6
$\begingroup$

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

$\endgroup$

1 Answer 1

8
$\begingroup$

It's not true. Please accept this humble paint counter-example.

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.

$\endgroup$
1
  • $\begingroup$ Awesome counter-example! Thanks! $\endgroup$
    – mchristos
    May 3, 2015 at 10:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .