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.

| cite | improve this answer | |
  • $\begingroup$ thanks! well, I thought that the maximum degree of the square of a graph is twice that of the original graph, by looking at cases like the square of cycles and trees. What about the half-square graphs of a bipartite graph? I think at least in that case we can bound the chromatic number in linear way $\endgroup$ – vidyarthi Jul 3 at 5:34
  • 1
    $\begingroup$ The finite projective plane gives a quadratic chromatic number even if you just take the half square. $\endgroup$ – Gjergji Zaimi Jul 3 at 5:37
  • $\begingroup$ Would it be of any use if the major degree vertices induce a forest, like in $K_{m,n}\ \ m\neq n$? $\endgroup$ – vidyarthi Jul 3 at 11:48

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.