Chromatic Numbers of Exact Distance Graphs

Abstract

For any graph $G=(V,E)$ and positive integer $p$, the exact distance-$p$ graph $G^{[♮p]}$ is the graph with vertex set $V$, which has an edge between vertices $x$ and $y$ if and only if $x$ and $y$ have distance $p$ in $G$. For odd $p$, Nešetřil and Ossona de Mendez proved that for any fixed graph class with bounded expansion, the chromatic number of $G^{[♮p]}$ is bounded by an absolute constant. Using the notion of generalised colouring numbers, we give a much simpler proof for the result of Nešetřil and Ossona de Mendez, which at the same time gives significantly better bounds. In particular, we show that for any graph $G$ and odd positive integer $p$, the chromatic number of $G^{[♮p]}$ is bounded by the weak $(2p-1)$-colouring number of $G$. For even $p$, we prove that $\chi (G^{[♮p]})$ is at most the weak $(2p)$-colouring number times the maximum degree. For odd $p$, the existing lower bound on the number of colours needed to colour $G^{[♮p]}$ when $G$ is planar is improved. Similar lower bounds are given for $K_t$-minor free graphs.

21 pages, 3 figures; error in proof corrected plus some minor changes