In continuation of the [previous](https://mathoverflow.net/questions/364614/chromatic-number-of-square-of-a-tree) 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.



Bound on the chromatic number of square of bipartite graphs
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.


