Three Coloring of a Graph

Question

Suppose that we have a graph $G = (V,N)$ and it is know that $G$ is three colorable. We also know that that there are distinct vertices $n_1$, $n_2$, $n_3$ and $n_4$ in $G$.

We know that there is a valid $3$ coloring of $G$ where vertices $n_1$ and $n_2$ are assigned the same color. We also know that there is a valid $3$ coloring of $G$ where vertices $n_3$ and $n_4$ are assigned the same color. Does this imply that there is a coloring of $G$ such that $n_1$ and $n_2$ are assigned the same color and $n_3$ and $n_4$ are assigned the same color?

Bob

Answer 1

Here is a counterexample with $6$ vertices and $8$ edges.

First consider the $2$-chromatic graph $H=P_2+P_3$ with vertices $u_1,u_2,w_1,w_2,w_3$ and edges $u_1u_2,w_1w_2,w_2w_3.$ Note that there is a proper $2$-coloring of $H$ where vertices $u_1$ and $w_1$ are assigned the same color, and there is also a proper $2$-coloring of $H$ where vertices $u_2$ and $w_3$ are assigned the same color, but there is no proper $2$-coloring of $H$ such that $u_1$ and $w_1$ are assigned the same color and vertices $u_2$ and $w_3$ are assigned the same color.

Let $G$ be the $3$-chromatic graph obtained from $H$ by adding a new vertex $v$ and edges joining $v$ to all vertices of $H.$ Then there is a proper $3$-coloring of $G$ where vertices $u_1$ and $w_1$ are assigned the same color, and there is also a proper $3$-coloring of $G$ where vertices $u_2$ and $w_3$ are assigned the same color, but there is no proper $3$-coloring of $G$ such that $u_1$ and $w_1$ are assigned the same color and vertices $u_2$ and $w_3$ are assigned the same color.

Answer 2

I believe the answer is no. Consider the following graph, in which $n_1$ and $n_2$ are drawn as squares, and $n_3$ and $n_4$ are drawn as diamonds.

The left picture shows $n_3$ and $n_4$ with the same colors; the right shows $n_1$ and $n_2$ with the same colors.

But the little assembly at the top ensures that $n_3$ and $n_2$ (the top diamond and the square just below it) have the same color, while the vertical line near the bottom ensures that $n_1$ and $n_4$ have different colors.