# Bound on the chromatic number of square of bipartite graphs

In continuation of the previous question, what is a strict upper bound on the chromatic number of the square of a bipartite graph?

I think the chromatic number number of the square of the bipartite graph with maximum degree $$\Delta=2$$ and a cycle is at most $$4$$ and with $$\Delta\ge3$$ is at most $$\Delta+1$$. This is because the edge set of a connected bipartite graph consists of the edges of a union of trees and a edge disjoint union of even cycles (with or without chords). Now, the square of a cycle requires at most $$4$$ colors, and the square of a tree requires at most $$\Delta+1$$ colors. Thus, the required number of colors is $$\Delta+1$$ in the latter case. Am I right here? Any counterexamples? Thanks beforehand.

The maximum degree of $$G^2$$ for general $$G$$ is at most $$\Delta^2$$, so we immetiately get an upper bound $$\chi(G^2)\le \Delta^2+1$$.
An example that is close to optimal is the incidence graph of the points and lines of a finite projective plane of order $$q$$. Here we have $$2(q^2+q+1)$$ vertices and the graph is regular of degree $$\Delta=q+1$$. The square of this graph has maximal cliques of size $$q^2+q+1$$ and in fact this is also equal to the chromatic number, so $$\chi (G^2)=\Delta^2-\Delta+1$$. In particular you shouldn't expect a linear bound in $$\Delta$$ without further conditions.
• Would it be of any use if the major degree vertices induce a forest, like in $K_{m,n}\ \ m\neq n$? – vidyarthi Jul 3 at 11:48