-2
$\begingroup$

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$?

$\endgroup$
1
  • 7
    $\begingroup$ Try a 5-cycle and see for yourself. $\endgroup$ Oct 11, 2017 at 13:00

2 Answers 2

4
$\begingroup$

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

https://en.wikipedia.org/wiki/Triangle-free_graph#Coloring_triangle-free_graphs

$\endgroup$
0
2
$\begingroup$

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$.

$\endgroup$

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