2
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I don't get "two by two". What does it mean? $\endgroup$ – Brendan McKay Mar 8 at 14:43
  • $\begingroup$ It means that any two paths in the set must have this property (be internally vertex-disjoint). $\endgroup$ – Arjuna196 Mar 8 at 14:56
  • $\begingroup$ 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.) $\endgroup$ – Brendan McKay Mar 8 at 15:16
  • $\begingroup$ Thanks for the tip. I edited the statement. $\endgroup$ – Arjuna196 Mar 8 at 19:28
1
$\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$.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Arjuna196 Mar 10 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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