0
$\begingroup$

In graph coloring I have heared the inequality $\chi(G) \le \omega(G) ^2$ where $\chi$ is graph chromatic number and $\omega$ is graph clique number in an arbitary graph G but actually I'm not sure whether it's true as far as I wasn't succesful proving it.
I would appreciate if you could clarify.

$\endgroup$

closed as unclear what you're asking by Shaun, user91500, Claude Leibovici, Shailesh, Arnaud D. Apr 10 '17 at 15:08

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What do you mean by the symbol $\omega^2$? $\endgroup$ – Laars Helenius Apr 9 '17 at 19:04
  • 1
    $\begingroup$ @LaarsHelenius In graph theory $\omega$ is the maximal sub graph which is a clique. $\endgroup$ – Smile Apr 9 '17 at 19:08
2
$\begingroup$

It's false: the Mycielski graph construction (Wikipedia link) shows that there exist graphs $G$ with $\chi(G)$ arbitrarily large but $\omega(G)=2$.

We do have $\chi(G) = \omega(G)$ when $G$ is a perfect graph. (This is sort of a by-definition claim, but perfect graphs are now known to be characterized by the strong perfect graph theorem, giving my statement some content.)

And, of course, we always have $\chi(G) \ge \omega(G)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.