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.
Best Answer
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.)