Dgdrxrt

I formulated the following 'conjecture' that might well be false, or well-known or both.

Let $G = (V_1 cup V_2, E)$ be a bipartite graph with 'parts' $V_1$ and $V_2$ and let $G_2$ be the distance-2-graph of $G$, that is: the graph on $V_1 cup V_2$ where $u$ and $v$ are connected iff in the original graph $G$ the distance between $u$ and $v$ is exactly 2. Let $Delta_1$ and $Delta_2$ denote the maximum degrees in $G$ of vertices in $V_1$ and $V_2$ respectively. Then

Conjecture 1: $chi(G_2) leq Delta_1 + Delta_2 - 1$

(i.e. the vertices in $G$ can be colored with $Delta_1 + Delta_2 - 1$ colors so that no two vertices at distance 2 from each other have the same color.)

As said I have no idea whether this is true. I have a bit more faith in the weaker conjecture:

Conjecture 2: $omega(G_2) leq Delta_1 + Delta_2 - 1$

(i.e. $G_2$ has no cliques of size $Delta_1 + Delta_2$)

Question: has anyone seen any of the conjectures before, or know whether or not they are true?

Background:

This is a bit silly really but some 15 years after first learning them I got suddenly struck by the similarity between the following two famous theorems

Theorem 1. Let $H$ be a graph with maximum degree $Delta$, then $chi(H) leq Delta + 1$. (So the vertices of $H$ can be colored with $Delta + 1$ colors.)

Theorem 2. Let $H$ be a graph with maximum degree $Delta$, then $chi'(H) leq Delta + 1$. (So the edges of $H$ can be colored with $Delta + 1$ colors.)

The similarity is even more remarkable given that the proof of Theorem 2 is long and complicated while the proof of Theorem 1 is nearly trivial.

Intrigued by the similarity I tried to formulate an 'overarching' theorem that would have both Theorems 1 and 2 as special cases. (Just for fun: it is clear that this wouldn't serve any didactic purpose: most likely the proof of the new theorem would be at least as hard as that of Theorem 2 so that proving Theorem 1 via this new theorem would be complete overkill and obscuring the underlying simplicity.) I tried several 'candidate theorems' but Conjecture 1 above is a bit of a favorite because it makes a plausible sounding statement about a much wider class of graphs.

To deduce Theorems 1 and 2 from Conjecture 1, we do the following. Let $V_1$ and $V_2$ be the vertex set and edge set of $H$ respectively and draw an edge in $G$ from $v in V_1$ to $e in V_2$ whenever vertex $v$ lies on edge $e$ in $H$.

Now $Delta_1 = Delta$ while $Delta_2 = 2$ so that the bound in the conjecture reduces to $Delta + 1$. $G_2$ naturally falls apart into two connected components (the induced subgraphs on $V_1$ and $V_2$ respectively) and if Conjecture 1 is true the bound of $Delta + 1$ on the coloring number holds for both. Now the bound on the coloring of $V_1$ given by the conjecture yields Theorem 1 and the bound on the coloring of $V_2$ yields Theorem 2.

With a little modification this argument can be reversed to show that Conjecture 1 holds whenever $max(Delta_1, Delta_2) leq 2$. The smallest 'new' case is then the case $Delta_1 = Delta_2 = 3$. I verified conjecture 2 for this case with brute force by hand, but don't really know how to start attacking Conjecture 1 here. Any help is appreciated.

Here is a counterexample to both of your conjectures.

Let $A = a_ij : 1 le i,j le n$ and $B = b_ij : 1 le i,j le n$. Define a bipartite graph $G$ between $A$ and $B$ by adding an edge between $a_ij$ and $b_kl$ whenever $i=k$ or $j=l$. This graph is regular of degree $2n-1$.

The distance-$2$ graph $G_2$ consists of two cliques of size $n^2$: one with vertex set $A$, and one with vertex set $B$. Any two vertices $a_ij, a_kl$ in $A$ are connected by the length-$2$ path $a_ij to b_kj to a_kl$ in $G$, so they are adjacent in $G_2$.

Therefore $chi(G_2) = omega(G_2) = n^2$, which is much larger than $Delta_1 + Delta_2 - 1 = 4n-3$, at least for large $n$.

Probably the extremal graph of this type is the incidence graph of a finite projective plane. For every prime power $q$, we can take a projective plane of order $q$, with $q^2+q+1$ points and $q^2+q+1$ lines. Then let $G$ be the bipartite graph with points on one side, lines on the other, and an edge connecting each point to the lines through it. This has $Delta_1 = Delta_2 = q+1$, and $chi(G_2) = omega(G_2) = q^2+q+1$, because once again $G_2$ consists of two cliques. Through any two points, there is a line, and any two lines intersect in a point - when translated to a statement about $G$, these two properties just say that any two vertices in the same part are distance $2$ apart.

Also, note that if Conjecture 1 were true even when $Delta_2 = 2$, it would imply not only Vizing's theorem (your Theorem 2) but also the same result for edge colorings of multigraphs with maximum degree $Delta$. But that result is false: consider the multigraph $H$ on three vertices $a,b,c$ with $k$ copies of each possible edge. Here, $Delta(H) = 2k$ but $chi'(H) = 3k$. (A theorem of Shannon says that this example is worst possible: $chi'(H) le frac32 Delta(H)$ for multigraphs.)