Is it true that one can always colour a graph G with $\chi(G)$ colours in such a way that one of the colour classes is a maximum possible cardinality independent set? Please prove if it's true.
[Note: $\chi(G)$ is the chromatic number of G, or the smallest number k such that we can colour the graph G with k colours. Independent set means none of the vertices in the set are adjacent.]
Best Answer
It's not true. Please accept this humble paint counter-example.
On the left, we see that the graph is 3-colorable. On the right, we take the maximum cardinality independent set and make it all blue, then get stuck with the remaining two colors.