3
$\begingroup$

I've also posted this problem in Math Stack Exchange (here), and it now has an answer in there.

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.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

This statement is true when $\chi(G) \leq 4$, and false when $\chi(G) \geq 5$. The proof of the first statement is long and sprawling, for which I apologise.

Notation: Throughout the post, for non-adjacent vertices $x$ and $y$, we use $\kappa(x,y)$ to denote the minimum cardinality of an $x-y$ separator. By Menger's Theorem, our graph under consideration will have a family of $\kappa(x,y)$ internally disjoint $x-y$ paths. Given a vertex $u$, we use $X_u$ to denote the set of all vertices entangled with $u$.

False for chromatic number 5 or more. Given an integer $n\geq 5$, we construct a graph $H_n = (V,E)$ with $\chi(H_n) = n$, that contains vertices $u$ and $v$ such that $X_u = \{u,v\}$ and $\kappa(u,v) = 3$. Let $V = \{u,v,x\}\sqcup A \sqcup B \sqcup C$, where $A$ and $C$ are sets of $n-2$ vertices, and $B$ is a set of $2$ vertices. Make $A$, $B$ and $C$ cliques. Let $u$ be adjacent to every vertex of $A$, every vertex of $A$ adjacent to every vertex of $B$, every vertex of $B$ adjacent to every vertex of $C$, and every vertex of $C$ adjacent to $v$. Finally, let $x$ be adjacent to $u$, $v$ and every vertex of $A$. By inspection, $\chi(H_n) = n$. To see that $H_n$ is as promised, we say without loss of generality that the vertices of $B$ get colours $1$ and $2$. It is then clear that either $c(x) = 1$ and $c(u)=c(v)=2$, or $c(x) = 2$ and $c(u)=c(v)=1$, so $u$ and $v$ are entangled with eachother, but not with any vertex of $B$, so $X_u = \{u,v\}$. Further, $B\cup \{x\}$ is a $u-v$ separator, so $\kappa(u,v) = 3$. This is inspired by the construction given in this answer.

enter image description here

True for chromatic number 4 or less. We need some new machinery. We say that a vertex $u$ and a set $S$ of vertices in a graph $G$ are weakly entangled if in every optimal colouring $c$ of $G$, there exists a vertex $w_c$ in $S$ such that $c(u)=c(w_c)$.

Lemma 1. Let $u$ and $v$ be entangled vertices in an $n$-chromatic graph $G$. If $S$ is a $u-v$ separator with $|S|\leq n-2$, then $u$ and $S$ are weakly entangled.

Proof. Assume to the contrary that $G$ has an optimal colouring $c$ such that $c(u)\neq c(w)$ for all $w$ in $S$, and let $G_v$ be the component of $G-S$ containing $v$. Since $|S|\leq n-2$, we may assume without loss of generality that $\{c(w) : w\in S\}\subseteq \{1,2,\dots,n-2\}$ and that $c(u)=c(v)=n-1$. Since no vertex of $S$ receives colour $n-1$ or $n$, we may swap these two colours in $G_v$ to obtain a new optimal colouring of $G$. In this new colouring, $c(u)=n-1$ and $c(v) = n$, contradicting their entanglement. QED.

Lemma 2. If $u$ and $v$ are entangled vertices in a graph $G$ with $\chi(G)\geq 3$, then $\kappa(u,v) > 1$.

You can prove Lemma 2 using the same "assume not, and swap colours on one side of the separator" as in the proof of Lemma 1.

Proposition 3. Your statement is true for any graph $G$ with $\chi(G) \leq 3$.

Proof. This is trivial for $\chi(G)\leq 2$. For $\chi(G) = 3$, your statement follows from Lemma 2 and Menger's Theorem.

This leaves us with the hard case in which $\chi(G)=4$. Lemmas are needed.

Lemma 4. Let $G$ be a graph with $\chi(G)\geq 4$. If $u$ and $v$ are entangled vertices, and $S$ is a $u-v$ separator with $|S|=2$, then $S\cap X_u \neq \emptyset$ (i.e., the separator contains a vertex entangled with $u$).

Proof. Assume to the contrary that $S=\{x,y\}$ is a $u-v$ separator and that neither $x$ nor $y$ are entangled with $u$. We assume without loss of generality that in every optimal colouring of $G$, the vertices $u$ and $v$ get colour 1. By Lemma 1, at least one of $x$ and $y$ get colour 1 in every optimal colouring of $G$. Since we can permute colours, we may also assume that in every optimal colouring $c$, we have that $\{c(x), c(y)\}\subseteq \{1,2\}$. By our assumption to the contrary, there must exist optimal colourings $c_1$ and $c_2$ such that $c_1(x)=c_2(y) = 1$ and $c_1(y)=c_2(x) = 2$ (if no such colourings existed, then $u$ would be entangled with at least one of $x$ and $y$). Let $c_2'$ be the colouring obtained from $c_2$ by swapping colours 1 and 2. Let $G_u$ and $G_v$ be the components of $G-S$ containing $u$ and $v$ respectively. Observe that $c_1$ and $c_2'$ agree on $S$. By colouring $G_u\cup S$ with $c_1$ and colouring $G_v\cup S$ with $c_2'$, we obtain an optimal colouring of $G$ in which $u$ and $v$ have different colours, contradicting their entanglement. QED.

Theorem 5. Let $G$ is a graph with $\chi(G)=4$, and let $u$ be a vertex of $G$. If $|X_u| \geq 2$, then there exists some vertex $w$ in $X_u$ such that $\kappa(u,w)\geq 3$.

Proof. We may assume that $G$ is 2-connected (we can discard everything apart from some block of $G$ that contains $u$ and some other vertex of $X_u$). Let $v$ be a vertex of $X_u-\{u\}$ that minimises $d(u,v)$, and assume contrary to the Theorem statement that for all $w\in X_u$, we have $\kappa(u,w) = 2$. Among all the $u-v$ separators with exactly two vertices in $G$, let $S=\{x,y\}$ be a separator that minimises the distance $d(u,S)$, and assume without loss of generality that $d(u,x) = d(u,S)$. We further choose $S$ such that among all two-vertex $u-v$ separators containing $x$, the distance between $u$ and the vertex $y$ in $S-\{x\}$ is as small as possible. (All in all, we have minimised $d(u,v)$, then minimised $d(u,x)$ given the choice of $v$, then minimised $d(u,y)$ given the choices of $v$ and $x$).

Since $S$ separates $u$ and $v$, any geodesic from $u$ to $v$ must contain a vertex of $S$. By Lemma 4 and the minimality of $v$, we deduce that the vertex $x$ lies on all $u-v$ geodesics and is not in $X_u$, and that the vertex $y$ is in $X_u$ (so $u$ and $y$ are entangled).

We now construct an auxillary graph to show that $\kappa(u,y)\geq 3$. First, let $C_u$ and $C_v$ be the components of $G-S$ containing $u$ and $v$ respectively, and let $G_u = G[C_u\cup S]$ be the subgraph of $G$ induced by the vertices of $C_u$ and $S$. Similarly let $G_v = G[C_v\cup S]$. Form a new graph $G^*$ from $G_u$ by adding a vertex $y'$ with $N(y') = N(y)$, and adding a vertex $z$ such that $N(z) = \{x,y,y'\}$ (see the diagram, we are "cloning" $y$).

enter image description here

Note that if $T$ is a $u-z$ separator in $G^*$, then $T-\{y'\}$ is a $u-v$ separator in $G$. By the minimality of distances from $u$ to $v$, $x$ and $y$, we thus deduce that $\kappa(u,z)\geq 3$ in $G^*$. So there exist internally disjoint $u-z$ paths $P_1$, $P_2$ and $P_3$ in $G^*$. Without loss of generality, $y$ and $y'$ are in $P_1: u, \dots, y, z$ and $P_2: u,\dots, y', z$, and $x$ is in $P_3$. By deleting the end vertex $z$ from $P_1$ and $P_2$, and replacing $y'$ with $y$, we get two internally disjoint $u-y$ paths from $P_1$ and $P_2$. By following $P_3$ from $u$ to $x$, and then following an $x-y$ path in $G_v$, we obtain a third internally disjoint path. QED.

Commentary: Lemma 4 is the linchpin here. In a 3-separator between entangled vertices, you can change which vertex gets the entangled colour in different optimal colourings (at least one vertex must get it by Lemma 1). In a 2-separator, you cannot.

$\endgroup$
2
$\begingroup$

Here is a proof to a related claim that hopefully will give you some ideas.

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.