Let us consider simple,finite, undirected graphs. A distance-two colouring of a graph $G$ is a fuction $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$ Mar 29 at 6:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.