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.



How many uniquely colored degree two vertices in 3-coloring of subcubic graph?
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.


