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

92 Views Asked by At

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.

In that question I made a false conjecture about the connectivity of entangled vertices. There I ask if

"Given a graph $G$ and two entangled vertices $u, v\in V(G)$, is there $w\in V(G)$ (possibly equal to $v$) also entangled with $u$ so that there are $\chi(G)-1$ disjoint paths from $u$ to $w$?"

It turns out that the conjecture is false for $\chi(G) \ge 5$, as shown by a counter example in that post. I would like to know now if the conjecture is true for the case $\chi(G) = 4$, i.e., if

"Given a $4$-chromatic graph $G$ and two entangled vertices $u, v\in V(G)$, is there $w\in V(G)$ (possibly equal to $v$) also entangled with $u$ so that there are $3$ disjoint paths from $u$ to $w$?"

In fact, it was this particular case that inspired me to come up with this conjecture. Any help would be greatly apreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

The conjecture is true for $\chi(G) = 4$.

I have posted an answer on math overflow, which feels like a more appropriate place for the rather involved proof.