Let $G$ be a simple graph with $n$ vertices. Let $\omega(G)$ and $\chi(G)$ denotes the clique number and chromatic number of $G$ respectively. Then

Does $\omega(G)\leq k$ imply $\chi(G)\leq k$ for $n\geq 3$?


closed as off-topic by Peter Mueller, Ilya Bogdanov, Goldstern, Chris Godsil, Gabriel C. Drummond-Cole Oct 11 '17 at 22:51

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Chris Godsil, Gabriel C. Drummond-Cole
  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Peter Mueller, Ilya Bogdanov, Goldstern
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 7
    $\begingroup$ Try a 5-cycle and see for yourself. $\endgroup$ – Gordon Royle Oct 11 '17 at 13:00

No, even triangle free graphs are counterexample since they can have arbitrary large chromatic number.



No. For the cycle graph $C_5$, $\chi(C_5)=3$, but $\omega(C_5)=2$. So for $k=2$, $\omega(C_5) \le k$ but it is not true that $\chi(C_5) \le k$.


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