<p>Let <span class="math-container">$\Delta$</span> denote the maximum degree of <span class="math-container">$G$</span>.</p>
<p>The bound <span class="math-container">$\Delta^2+1$</span> 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 <span class="math-container">$\Omega(\Delta^2/\log \Delta)$</span> [1].</p>
<p>Given below is a quote from a dynamic survey [2] of Cranston<br />
(the notation <span class="math-container">$\chi^2(G)$</span> is replaced by <span class="math-container">$\chi(G^2)$</span> for clarity).</p>
<blockquote>
<p>Greedy coloring shows that <span class="math-container">$χ(G) \leq ∆ + 1$</span> for all <span class="math-container">$G$</span>. Since <span class="math-container">$G^2$</span> has maximum degree at most <span class="math-container">$∆^2$</span> , we immediately have <span class="math-container">$χ(G^2) ⩽ ∆^2 + 1$</span>. Applying Brooks’ Theorem to <span class="math-container">$G^2$</span> shows that equality holds for a connected graph <span class="math-container">$G$</span> only if <span class="math-container">$G^2 = K_{∆^2+1}$</span> . Hoffman and Singleton [100] famously used linear algebra to show this is possible only if <span class="math-container">$∆ ∈ \{2, 3, 7, 57\}$</span>.
This proof is also outlined in [147, Section 3.1]. The unique realizations for <span class="math-container">$∆ = 2$</span> and <span class="math-container">$∆ = 3$</span> are the 5-cycle and the Petersen graph. For <span class="math-container">$∆ = 7$</span>, the only realization is the Hoffman-Singleton graph [100]. For <span class="math-container">$∆ = 57$</span>, the question of whether any realization exists remains a major open problem.</p>
</blockquote>
<h2>References</h2>
<p>[1] <em>Almeter, Jordan; Demircan, Samet; Kallmeyer, Andrew; Milans, Kevin G.; Winslow, Robert</em>, <a href="https://doi.org/10.1007/s00373-018-1979-4" rel="nofollow noreferrer"><strong>Graph 2-rankings</strong></a>, Graphs Comb. 35, No. 1, 91-102 (2019). <a href="https://zbmath.org/?q=an:1407.05186" rel="nofollow noreferrer">ZBL1407.05186</a>.</p>
<p>[2] <em>Cranston, Daniel W.</em>, <a href="https://doi.org/10.37236/10898" rel="nofollow noreferrer"><strong>Coloring, list coloring, and painting squares of graphs (and other related problems)</strong></a>,  <a href="https://zbmath.org/?q=an:07727365" rel="nofollow noreferrer">ZBL07727365</a>.</p>

CC BY-SA 4.0
2023-08-24T04:46:14.127Z
The graphs $G$ for which $G^2=K_{\Delta^2+1}$ are precisely the Moore graphs of diameter 2.
Cyriac Antony
CC BY-SA 4.0
2023-08-23T11:25:45.203Z
2023-08-23T11:25:45.203Z
Cyriac Antony
<p>Let us consider simple,finite, undirected graphs. A distance-two colouring of a graph <span class="math-container">$G$</span> is a function <span class="math-container">$f:V(G)\to\{1,2,\dots\}$</span> such that <span class="math-container">$f(u)\neq f(v)$</span> whenever <span class="math-container">$dist_G(u,v)\leq 2$</span>. A distance-two colouring of <span class="math-container">$G$</span> is equivalent to a (proper) colouring of the square graph <span class="math-container">$G^2$</span> of <span class="math-container">$G$</span>. Obviously, at least <span class="math-container">$\Delta(G)+1$</span> colours are required for a distance-two colouring of <span class="math-container">$G$</span> (where <span class="math-container">$\Delta(G)$</span> denotes the maximum degree of <span class="math-container">$G$</span>). Also, every graph <span class="math-container">$G$</span> admits a distance-two colouring with <span class="math-container">$\Delta(G)^2+1$</span> colours (by greedy colouring of <span class="math-container">$G^2$</span>).<br />
<strong>Is there a better upper bound (at least for a restrcited graph class such as planar graphs) ?</strong><br />
<em>Or, is it not possible to obtain an <span class="math-container">$o(\Delta(G)^2)$</span> uppderbound, even for reasonably large restricted graph classes?</em></p>
<p>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 <span class="math-container">$(2,\mathcal{F})$</span>-subgraph colouring in the terminology of [1] where <span class="math-container">$\mathcal{F}=\{P_3\}$</span>; and using Theorem 1 of [1], we can only say that there is a constant <span class="math-container">$C\leq 64\times 3^3$</span> such that <span class="math-container">$C\Delta(G)^2$</span> colours suffices to produce a distance-two colouring of <span class="math-container">$G$</span>.</p>
<p>[1] <em>Aravind, N. R.; Subramanian, C. R.</em>, <a href="http://dx.doi.org/10.1007/978-3-642-10217-2_9" rel="nofollow noreferrer"><strong>Forbidden subgraph colorings and the oriented chromatic number</strong></a>, 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). <a href="https://zbmath.org/?q=an:1267.05111" rel="nofollow noreferrer">ZBL1267.05111</a>.</p>

CC BY-SA 4.0
2022-03-29T06:31:55.610Z
I am aware of Wagner's conjecture, and asking for proved results.
Cyriac Antony
<graph-theory><graph-colouring><upper-bounds>
Upper Bound for distance-two chromatic number in terms of maximum degree
Cyriac Antony
# Upper Bound for distance-two chromatic number in terms of maximum degree

(Asked by: username_0 on 2022-03-29)

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**](http://dx.doi.org/10.1007/978-3-642-10217-2_9), 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](https://zbmath.org/?q=an:1267.05111).

**Tags:** graph-theory, graph-colouring, upper-bounds

> **Comments:**
> **username_0**: I am aware of Wagner's conjecture, and asking for proved results.  

---

## 1 answers

### Answer by username_0 on 2023-08-23. Score: 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**](https://doi.org/10.1007/s00373-018-1979-4), Graphs Comb. 35, No. 1, 91-102 (2019). [ZBL1407.05186](https://zbmath.org/?q=an:1407.05186).

[2] *Cranston, Daniel W.*, [**Coloring, list coloring, and painting squares of graphs (and other related problems)**](https://doi.org/10.37236/10898), [ZBL07727365](https://zbmath.org/?q=an:07727365).

> **Comments:**
> **username_0**: The graphs $G$ for which $G^2=K_{\Delta^2+1}$ are precisely the Moore graphs of diameter 2.  

---

