Clique number and chromatic number

coloringdiscrete mathematicsgraph theory

It is known that $\chi(G) \geq \omega(G)$. However, graph theorists love to sharpen their bounds. Are there known sufficient conditions to ensure that $ \chi(G) = \omega(G)$, where $\omega(G)$ is the clique number (largest clique in simple undirected graph G) and $\chi(G)$ is the chromatic number of G? (A simple counter-example is an odd-cycle, where $\chi(G) = 3$ but $\omega(G) = 2$).

I was thinking that if your graph doesn't have more than 1 clique of size $\omega(G)$, then this has to be true.

Best Answer

Any Graph $G=(V, E)$ can be extended to a graph $G\prime=(V\prime, E\prime)$ satisfying $w(G\prime)=\chi(G\prime)$, simply by adding to $G$ a clique of size $\chi(G)$, disjoint from $V$.

But there are actually a bunch of graph classes ensuring this equality. For examples: bipartite graphs, comparability graphs, chordal graphs...

I refer to the book by Alexander Schrijver "Combinatorial Optimization" Chapter 65 & 66.