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

I did not get an answer when asking for help with this question in Math Stack Exchange (here). Anyway, I believe that this forum is more suitable for it.

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

Here, 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 pairwise internally vertex-disjoint paths from $$u$$ to $$w$$.

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 pairwise internally vertex-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$$. Because it is a stronger result this would be more convenient for me.

I would appreciate some help with this subject.

• I don't get "two by two". What does it mean? – Brendan McKay Mar 8 at 14:43
• It means that any two paths in the set must have this property (be internally vertex-disjoint). – Arjuna196 Mar 8 at 14:56
• Ok, then "pairwise" is more normal usage. But you don't actually need a word at all since "disjoint" means "pairwise disjoint". (Some people might argue.) – Brendan McKay Mar 8 at 15:16
• Thanks for the tip. I edited the statement. – Arjuna196 Mar 8 at 19:28

Claim. Let $$X$$ be an equivalence class of the entanglement relation on $$V(G)$$. Then for all distinct $$u,v \in X$$, there exist $$\chi(G)-1$$ edge-disjoint paths in $$G$$ between $$u$$ and $$v$$.
Proof. Let $$k=\chi(G)$$ and $$V_1, \dots, V_k$$ be a partition of $$V(G)$$ into stable sets. By relabelling, we may assume that $$X \subseteq V_1$$. Observe that all vertices of $$X$$ must be contained in some component of $$G[V_1 \cup V_2]$$. Otherwise, we may recolour to obtain a $$k$$-colouring of $$G$$ where two vertices of $$X$$ are coloured differently. In particular, for all distinct $$u,v \in X$$, there is a $$u$$--$$v$$ path in $$G[V_1, \cup V_2]$$. Repeating the argument for $$i=2, \dots, k$$, gives the $$k-1$$ edge-disjoint $$u$$--$$v$$ paths in $$G$$. $$\square$$
Note that the claim proves something stronger and weaker than what was asked in the original question. It is weaker because the paths are edge-disjoint not vertex-disjoint. But it is stronger since it holds for all distinct pairs $$u,v \in X$$. Moreover, the paths constructed in the proof are almost vertex-disjoint. The only vertices they have in common are in $$V_1$$.
• I noticed this fact. It was used for the demonstration that I mentioned in the statement, for the case where there is only one vertex entangled with $u$. I was inspired by the idea of ​​Kempe chains. – Arjuna196 Mar 10 at 13:56