Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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:
- Does there always exist a $3$-coloring that uses at most two colors for some maximum independent set of this graph?
- If the answer to question 1 is yes, can such a coloring be found in polynomial time?
It at least doesn't work out that for every maximum independent set there is a 3-coloring of the graph which 2-colors the independent set. Here is a counterexample to that stronger version of your question:
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.
It's fairly straightforward to show that there's no 3-coloring that 2-colors the independent set. Let's try to color the vertices in the independent set Red or Blue, leaving Green as the third color, and derive a contradiction. We'll start at the bottom: the triangle there (with the red edge) needs to have one vertex of each color. Since the top vertex in the triangle can't be Green, then, by symmetry, we can assume wlog that the bottom left vertex is assigned Green. This forces the top of that same triangle to be Red-or-Blue, and the other vertex of the triangle to be Blue-or-Red (the opposite). The bottom right vertex being Blue-or-Red then forces the vertex above it to be Red-or-Blue. The two white vertices both being Red-or-Blue force the left vertex of the inner triangle (with all black edges) to be Red-or-Blue. This in turn forces the remaining white vertex in the bottom half to be assigned Blue-or-Red. The top two white vertices in the bottom half are then Red-or-Blue and Blue-or-Red, which forces the top-most black vertex in the bottom half to be Green. Repeating this argument for the top half, we eventually get that the edge that bridge the two halves is Green on both sides, a contradiction.
