Let us consider simple,finite, undirected graphs. A distance-two colouring of a graph $G$ is a function $f:V(G)\to\{1,2,\dots\}$ such that $f(u)\neq f(v)$ whenever $dist_G(u,v)\leq 2$. A distance-two colouring of $G$ is equivalent to a (proper) colouring of the square graph $G^2$ of $G$. Obviously, at least $\Delta(G)+1$ colours are required for a distance-two colouring of $G$ (where $\Delta(G)$ denotes the maximum degree of $G$). Also, every graph $G$ admits a distance-two colouring with $\Delta(G)^2+1$ colours (by greedy colouring of $G^2$).
Is there a better upper bound (at least for a restrcited graph class such as planar graphs) ?
Or, is it not possible to obtain an $o(\Delta(G)^2)$ uppderbound, even for reasonably large restricted graph classes?

Note that with the help of entropy compression method, good bounds are obtained for acyclic/star chromatic numbers (and acyclic/star chromatic indices). But, this approach seems not to be of use for distance-two colouring. For example, distance-two colouring is a $(2,\mathcal{F})$-subgraph colouring in the terminology of [1] where $\mathcal{F}=\{P_3\}$; and using Theorem 1 of [1], we can only say that there is a constant $C\leq 64\times 3^3$ such that $C\Delta(G)^2$ colours suffices to produce a distance-two colouring of $G$.

[1] Aravind, N. R.; Subramanian, C. R., Forbidden subgraph colorings and the oriented chromatic number, Fiala, Jiří (ed.) et al., Combinatorial algorithms. 20th international workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-10216-5/pbk). Lecture Notes in Computer Science 5874, 60-71 (2009). ZBL1267.05111.

  • $\begingroup$ I am aware of Wagner's conjecture, and asking for proved results. $\endgroup$ Commented Mar 29, 2022 at 6:31

1 Answer 1


Let $\Delta$ denote the maximum degree of $G$.

The bound $\Delta^2+1$ cannot be improved significantly. For instance, even for a colouring variant called 2-ranking (which is a generalisation of distance-two colouring), the number of colours required is $\Omega(\Delta^2/\log \Delta)$ [1].

Given below is a quote from a dynamic survey [2] of Cranston
(the notation $\chi^2(G)$ is replaced by $\chi(G^2)$ for clarity).

Greedy coloring shows that $χ(G) \leq ∆ + 1$ for all $G$. Since $G^2$ has maximum degree at most $∆^2$ , we immediately have $χ(G^2) ⩽ ∆^2 + 1$. Applying Brooks’ Theorem to $G^2$ shows that equality holds for a connected graph $G$ only if $G^2 = K_{∆^2+1}$ . Hoffman and Singleton [100] famously used linear algebra to show this is possible only if $∆ ∈ \{2, 3, 7, 57\}$. This proof is also outlined in [147, Section 3.1]. The unique realizations for $∆ = 2$ and $∆ = 3$ are the 5-cycle and the Petersen graph. For $∆ = 7$, the only realization is the Hoffman-Singleton graph [100]. For $∆ = 57$, the question of whether any realization exists remains a major open problem.


[1] Almeter, Jordan; Demircan, Samet; Kallmeyer, Andrew; Milans, Kevin G.; Winslow, Robert, Graph 2-rankings, Graphs Comb. 35, No. 1, 91-102 (2019). ZBL1407.05186.

[2] Cranston, Daniel W., Coloring, list coloring, and painting squares of graphs (and other related problems), ZBL07727365.

  • $\begingroup$ The graphs $G$ for which $G^2=K_{\Delta^2+1}$ are precisely the Moore graphs of diameter 2. $\endgroup$ Commented Aug 24, 2023 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.