# 3-color a cubic graph such that a MIS receives only two colors

According to Brooks'_theorem, a cubic graph (3-regular graph) containing no $K_4$ can be properly colored by three colors. (Such a color can actually be found in linear time, which is not our primary concern.)

The questions are:

1. Does there always exist a $3$-coloring that uses at most two colors for some maximum independent set of this graph?
2. If the answer to question 1 is yes, can such a coloring be found in polynomial time?
• I just got curious: is there a motivation for this question? – Vinicius dos Santos Jun 5 '16 at 5:00
• @ViniciusdosSantos Here is our motivation (arxiv.org/abs/1606.08141, page 8 paragraph 3), though not a good one. – Yixin Cao Jun 30 '16 at 8:19

The circles represent vertices. You can also easily check that the graph is 3-regular and isn't $K_4$. Open circles define the maximum independent set which gives the counterexample. (Unfortunately, there are many other non-isomorphic maximum independent sets in this graph, and at least one of them does get 2-colored by some 3-coloring of the graph.) It's not too hard to see that each of the two "halves" that make up this graph can have an independent set of size at most three, and hence the graph as a whole has all independent sets having size at most six. Thus the independent set given here is indeed maximum.