Upper Bound for distance-two chromatic number in terms of maximum degree

Question

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.

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.

References

[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.