A problem about the connectivity of vertices that must have the same color for any proper minimal coloring of a graph.

204 Views Asked by At

The question is now also published in MathOverflow (here).

I'm trying to solve a problem about connectivity of entangled vertices in a graph.

Two vertices $u, v$ of a finite graph $G(V, E)$ are said to be entangled if for any proper coloring $c:V(G)\rightarrow\mathbb{N}$ with $\chi(G)$ colors we have $c(u) = c(v)$, that is, they must have the same color.

What I'm trying to prove is that, given two entangled vertices $u, v\in V(G)$, there is $w\in V(G)$ (possibly equal to $v$) also entangled with $u$ so that there is a set of size $\chi(G)-1$ of disjoint paths from $u$ to $w$.

EDIT: The proof cited below was incorrect, as shown by the accepted answer.

I was able to prove, using the vertex-connectivity version of Menger's theorem and induction, that the previous statement is true if $v$ is the only vertex in $G$ entangled with $u$, so I've been trying to show that if there is not a set of size $\chi(G)-1$ of disjoint paths from $u$ to $v$ (considering $u$ and $v$ entangled), there is still a vertex in $G-v$ entangled with $u$, but without success.

Another idea I had was showing that the minimal (in the number of edges) subgraph of $G$ for which there is still a vertex entangled with $u$, has exactly one vertex entangled with $u$.

I would appreciate some help with this subject.

1

There are 1 best solutions below

0
On BEST ANSWER

I believe your statement holds for $\chi(G) \leq 3$ but can fail for $\chi(G) = 5$. (I tried but failed to find a counterexample with $\chi(G) = 4$, and I'd be interested to see an example or a proof there.)

Here's the example I constructed for $\chi(G) = 5$. I claim that vertices $x$ and $y$ are entangled, but that there are not $4$ internally-disjoint paths between them: enter image description here

To see that we can't find 4 internally-disjoint paths, it suffices to observe that the vertices with thick lines form an $x,y$-separating set of size 3. Now to see that $x,y$ are entangled, consider extending the generic precoloring of the $K_5$ on the left. We must have $v_1$ and $v_2$ taking the colors red and blue in some order, since they form a $K_5$ with the green/yellow/purple vertices. Hence $w_1, w_2, w_3$ must take green/yellow/purple as well, in some order. Now $y$ and $z$, forming a $K_5$ with $w_1, w_2, w_3$, must also take red and blue in some order; but since $y$ is adjacent to the leftmost blue vertex, that means $y$ is forced to be red. Thus $x$ and $y$ are entangled.

Finally, observe that $y$ is the only vertex entangled with $x$, because we can always swap the colors on $v_1$ and $v_2$: one of them has to be red in any proper $5$-coloring, but we get to choose which one.