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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .