8
$\begingroup$

Is there a graph with maximum degree three that has 3 degree two vertices that must get the same (resp. different) color in every 3-coloring of the graph?

I'm interested in any similar results as well.

ps. Note that if we change the maximum degree to four, then it is easy to construct such graphs. Just take a long path and double every other vertex, connecting it to its old neighbors and the two copies with each other. Then you can add a degree two vertex connected to both copies for each doubled vertex.

$\endgroup$
8
$\begingroup$

No such graph exists (that is, you cannot have a subcubic graph with three degree-$2$ vertices all forced to the same color). Suppose that such a graph exists; we may assume the graph is connected. The vertices of degree $2$ forced to the same color must be pairwise nonadjacent (otherwise, your graph has no $3$-coloring at all, contradicting Brooks' Theorem). Add a new edge among any two of these vertices to form a new graph $G'$; now $G'$ is subcubic and has no proper $3$-coloring. Since there are still missing edges from the other degree-$2$ vertex to the endpoints of the new edge, $G'$ is not a complete graph, but by Brooks' Theorem, any connected subcubic graph that is not a complete graph has a proper $3$-coloring.

Similarly, you cannot have a connected subcubic graph with three degree-$2$ vertices all forced to different colors in every $3$-coloring, unless that graph is a triangle: add a new vertex adjacent to those three vertices to form a new subcubic graph $G'$ with no proper $3$-coloring. If your original graph is not a triangle, then $G'$ is not a complete graph, so Brooks' Theorem again gives a contradiction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Such a simple reduction, thx! $\endgroup$ – domotorp Feb 6 '16 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.