# Chromatic Numbers of Exact Distance Graphs ††thanks:  The research for this
paper was started during a stay of the first two authors at the Mittag-Leffler
Institute in Stockholm. JvdH and HAK would like to thank the Mittag-Leffler
Institute for hospitality and support.

Jan van den Heuvel, H.A. Kierstead and Daniel A. Quiroz 22footnotemark: 2
Department of Mathematics, London School of Economics and Political Science,
London WC2A 2AE, UK. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>School of Mathematical and Statistical Sciences, Arizona State University,
Tempe, AZ 85287, USA. Email<EMAIL_ADDRESS>
###### Abstract

For any graph $G=(V,E)$ and positive integer $p$, the _exact distance- $p$
graph_ $G^{[\natural 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^{[\natural
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^{[\natural p]}$
is bounded by the weak $(2p-1)$-colouring number of $G$. For even $p$, we
prove that $\chi(G^{[\natural 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^{[\natural p]}$ when $G$ is planar is improved. Similar lower bounds
are given for $K_{t}$-minor free graphs.

Key Words: _bounded expansion, chromatic number, exact distance graphs,
generalised colouring numbers, planar graphs_

##  1 Introduction and Main Results

###  1.1 Powers, exact powers, and exact distance graphs

All graphs in this paper are assumed to be finite, undirected, simple and
without loops. For a graph $G=(V(G),E(G))$ (or just $(V,E)$ if the graph under
consideration is clear) and vertices $x,y\in V$, let $d_{G}(x,y)$ denote the
distance between $x$ and $y$ in $G$, that is, the number of edges contained in
a shortest path between $x$ and $y$.

For a positive integer $p$, the _$p$ -th power graph $G^{p}=(V,E^{p})$ of $G$_
is the graph with $V$ as its vertex set and $E^{p}$ contains the edge $xy$ if
and only if $d_{G}(x,y)\leq p$. Problems related to the chromatic number
$\chi(G^{p})$ of power graphs $G^{p}$ were first considered by Kramer and
Kramer [13, 14] in 1969 and have enjoyed significant attention ever since. It
is clear that for $p\geq 2$ any power of a star is a clique, and hence there
are not many classes of graphs for which $\chi(G^{p})$ can be bounded by a
constant. An easy argument shows that for a graph $G$ with maximum degree
$\Delta(G)\geq 3$ we have

$\chi(G^{p})\leq 1+\Delta(G^{p})\leq
1+\Delta(G)\cdot\sum_{i=0}^{p-1}(\Delta(G)-1)^{i}\in\mathcal{O}(\Delta(G)^{p}).$

However, there are many classes of graphs for which it is possible to find
much better upper bounds. Recall that a graph $G$ is _$k$ -degenerate_ if
every subgraph of $G$ contains a vertex of degree at most $k$.

######  Theorem 1.1 (Agnarsson & Halldórsson [1]).

Let $k$ and $p$ be positive integers. There exists a constant $c=c(k,p)$ such
that for every $k$-degenerate graph $G$ we have $\chi(G^{p})\leq
c\cdot\Delta(G)^{\lfloor p/2\rfloor}$.

In this result, the exponent on $\Delta(G)$ is best possible (see below). In
particular, $\chi(G^{2})$ is at most linear in $\Delta(G)$ for planar graphs
$G$. Wegner [24] conjectured that every planar graph $G$ with $\Delta(G)\geq
8$ satisfies
$\chi(G^{2})\leq\bigl{\lfloor}\frac{3}{2}\Delta(G)\bigr{\rfloor}+1$, and gave
examples that show this bound would be tight. The conjecture has attracted
considerable attention since it was stated in 1977. For more on this
conjecture we refer the reader to [2, 15].

In [20, Section 11.9], Nešetřil and Ossona de Mendez define the notion of
_exact power graph_. Let $G=(V,E)$ be a graph and $p$ a positive integer. The
_exact $p$-power graph $G^{\natural p}$_ has $V$ as its vertex set, and $xy$
is an edge in $G^{\natural p}$ if and only if there is in $G$ a path of length
$p$ (i.e. with $p$ edges) between the vertices $x$ and $y$ (the path need not
be induced, nor a shortest path). Similarly, they define the _exact distance-
$p$ graph $G^{[\natural p]}$_ as the graph with $V$ as its vertex set, and
$xy$ as an edge if and only if $d_{G}(x,y)=p$. Since obviously $E(G^{[\natural
p]})\subseteq E(G^{\natural p})\subseteq E(G^{p})$, we have $\chi(G^{[\natural
p]})\leq\chi(G^{\natural p})\leq\chi(G^{p})$.

For planar graphs $G$, Theorem 1.1 gives that the exact $p$-power graphs
$G^{\natural p}$ satisfy $\chi(G^{\natural
p})\in\mathcal{O}\bigl{(}\Delta(G)^{\lfloor p/2\rfloor}\bigr{)}$. This result
is best possible, even for outerplanar graphs, as the following examples show.
For $k\geq 2$ and $p\geq 4$, let $T_{k,\lfloor p/2\rfloor}$ be the $k$-regular
tree of radius $\bigl{\lfloor}\frac{1}{2}p\bigr{\rfloor}$ with root $v$. We
say that a vertex $y$ is at level $\ell$ if $d(v,y)=\ell$. For every edge $uv$
between vertices at levels $\ell$ and $\ell+1$ for some $\ell\geq 1$, we do
the following: if $p$ is even, then add a path of length $\ell+1$ between $u$
and $v$; if $p$ is odd, then add paths of length $\ell+1$ and $\ell+2$ between
$u$ and $v$. Call the resulting graph $G_{k,p}$. It is straightforward to
check that $\Delta(G_{k,p})\leq 2k$ for even $p$, that $\Delta(G_{k,p})\leq
3k$ for odd $p$, and that there is a path of length $p$ between any two
vertices at level $\bigl{\lfloor}\frac{1}{2}p\bigr{\rfloor}$. Since there are
$k(k-1)^{\lfloor p/2\rfloor-1}$ vertices at level
$\bigl{\lfloor}\frac{1}{2}p\bigr{\rfloor}$, this immediately means that
$\chi(G_{k,p}^{\natural p})\geq k(k-1)^{\lfloor
p/2\rfloor-1}\in\Omega(\Delta(G_{k,p})^{\lfloor p/2\rfloor})$.

Surprisingly, for exact distance graphs, the situation is quite different.

######  Theorem 1.2.

(a)Let $p$ be an odd positive integer. Then there exists a constant $c=c(p)$
such that for every planar graph $G$ we have $\chi(G^{[\natural p]})\leq c$.

(b)Let $p$ be an even positive integer. Then there exists a constant
$c^{\prime}=c^{\prime}(p)$ such that for every planar graph $G$ we have
$\chi(G^{[\natural p]})\leq c^{\prime}\cdot\Delta(G)$.

The results in Theorem 1.2 are actually special cases of the following more
general results. We will recall the concept of a _graph class with bounded
expansion_ in the next subsection.

######  Theorem 1.3.

Let $\mathcal{K}$ be a class of graphs with bounded expansion.

(a)Let $p$ be an odd positive integer. Then there exists a constant
$C=C(\mathcal{K},p)$ such that for every graph $G\in\mathcal{K}$ we have
$\chi(G^{[\natural p]})\leq C$.

(b)Let $p$ be an even positive integer. Then there exists a constant
$C^{\prime}=C^{\prime}(\mathcal{K},p)$ such that for every graph
$G\in\mathcal{K}$ we have $\chi(G^{[\natural p]})\leq
C^{\prime}\cdot\Delta(G)$.

We will give two proofs of part (a). The two proofs give incomparable bounds.
Also, both proofs are considerably shorter and provide better bounds than the
original proof of part (a) of Nešetřil and Ossona de Mendez [20, Theorem
11.8]. Theorem 1.3 (b) is new, as far as we are aware.

As we showed above, if we consider exact powers instead of exact distance
graphs, then we need to use bounds involving $\Delta(G)$ if we want to bound
$\chi(G^{\natural p})$, even for odd $p$ and if $G$ is planar. However, by
adding the condition that $G$ has sufficiently large _odd girth_ (length of a
shortest odd cycle), $\chi(G^{\natural p})$ can be bounded without reference
to $\Delta(G)$, for odd $p$. It follows from Theorem 1.3 (a) that this is
possible if the odd girth is at least $2p+1$. This is because odd girth at
least $2p+1$ guarantees that if there is a path of length $p$ between $u$ and
$v$, then any shortest $uv$-path has odd length. With some more care we can
reprove the following.

######  Theorem 1.4 (Nešetřil & Ossona de Mendez [20, Theorem 11.7]).

Let $\mathcal{K}$ be a class of graphs with bounded expansion and let $p$ be
an odd positive integer. Then there exists a constant $M=M(\mathcal{K},p)$
such that for every graph $G\in\mathcal{K}$ with odd girth at least $p+1$ we
have $\chi(G^{\natural p})\leq M$.

Theorem 1.2 (a) and its general version Theorem 1.3 (a) are quite surprising,
since the exact distance graphs $G^{[\natural p]}$ of a planar graph $G$ can
be very dense. To see this, for $i\geq 2$ let $L_{i}$ be obtained from the
complete graph $K_{4}$ by subdividing each edge $i-1$ times (i.e. by replacing
each edge by a path of length $i$). For $k\geq 1$, form $L_{i,k}$ by adding
four sets of $k$ new vertices to $L_{i}$ and joining all $k$ vertices in the
same set to one of the vertices of degree three in $L_{i}$. See Figure 1 for a
sketch of $L_{1,k}$.

Figure 1:  A graph $L_{1,k}$ such that $L_{1,k}^{[\natural 3]}$ has edge
density approximately 3/4.

It is easy to check that $L_{i,k}$ is a planar graph with $4+6(i-1)+4k$
vertices, while $L_{i,k}^{[\natural(i+2)]}$ has $6k^{2}$ edges. So for fixed
$i$ and large $k$, the graph $L_{i,k}^{[\natural(i+2)]}$ has approximately
$3/4$ times the number of edges of the complete graph on the same number of
vertices.

It is interesting to see what actual upper and lower bounds we can get for the
chromatic numbers of $G^{[\natural p]}$ for $G$ from some specific classes of
graphs and for specific values of (odd) $p$. Using the proof in [20], it
follows that for $p=3$ and for planar graphs $G$ we can get the upper bound
$\chi(G^{[\natural 3]})\leq 5\cdot 2^{20,971,522}$ (see also Subsection 1.3).
On the other hand, [20, Exercise 11.4] gives an example of a planar graph $G$
with $\chi(G^{[\natural 3]})=6$.

Our new proof of Theorem 1.3 (a) already gives a much smaller upper bound for
$\chi(G^{[\natural 3]})$ for planar graph $G$. By a more careful analysis, we
can reduce that upper bound even further, giving the bound in the following
result. We also managed to increase the lower bound, although by one only.
Details can be found in Section 4.

######  Theorem 1.5.

(a)For every planar graph $G$ we have $\chi(G^{[\natural 3]})\leq 143$.

(b)There exists a planar graph $G_{5}$ such that $\chi(G_{5}^{[\natural
3]})=7$.

For outerplanar graphs $G$ we have that $\chi(G^{[\natural 3]})\leq 13$, while
there exists an outerplanar graph $G_{4}$ such that $\chi(G_{4}^{[\natural
3]})=5$ (see the results in Sections 3 and 4).

###  1.2 Generalised colouring numbers and main results

When solving an optimisation problem it is often useful to preorder the input
so as to minimise some parameter. One such parameter is the _colouring number_
$\mathrm{col}(G)$ of a graph $G$. This is the minimum integer $k$ such that
there is a linear ordering $L$ of $V$ such that every vertex $y$ has at most
$k-1$ neighbours $x$ with $x<_{L}y$. (So the colouring number is one more than
the _degeneracy_ of a graph.) It is well-known and easy to see that the
chromatic number $\chi(G)$ of a graph $G$ satisfies
$\chi(G)\leq\mathrm{col}(G)$. Although this bound is far from being tight in
many cases, it is often used to show that a specific class of graphs has
bounded chromatic number.

Different generalisations of the colouring number can be found in the
literature. Chen and Schelp [4] proved that the class of planar graphs has
linear Ramsey number by also controlling, for all vertices $v$, the number of
smaller vertices that can be reached by a path of length two, whose middle
vertex is larger than $v$. Various versions of their idea were applied by
Kierstead and Trotter [10], Kierstead [8], and Zhu [25] to problems concerning
the game chromatic number of graphs and gave rise to the 2-colouring number
defined below. In their study of oriented game chromatic number of graphs,
Kierstead and Trotter [11] considered paths of length four with different
configurations of “large” internal vertices, which later motivated the notions
of 4-colouring number and weak 4-colouring number. Kierstead and Kostochka [9]
applied 2-colouring numbers to a (non-game) packing problem.

All of these notions are encompassed in the concepts of the _$k$ -colouring
number_ and the _weak $k$-colouring number_ of a graph, both of which were
first introduced by Kierstead and Yang [12].

Let $G=(V,E)$ be a graph, $L$ a linear ordering of $V$, and $k$ a positive
integer. We say that a vertex $x\in V$ is _$k$ -accessible_ from $y\in V$ if
$x<_{L}y$ and there exists an $x,y$-path $P$ of length at most $k$ such that
$y<_{L}z$ for all internal vertices $z$ of $P$. Similarly, if all internal
vertices $z$ of $P$ satisfy the less restrictive condition that $x<_{L}z$,
then we say that $x$ is _weakly $k$-accessible_ from $y$. Let $R_{L,k}(y)$ be
the set of vertices that are $k$-accessible from $y$, and $Q_{L,k}(y)$ the set
of vertices that are weakly $k$-accessible from $y$. The _$k$ -colouring
number $\mathrm{col}_{k}(G)$_ and _weak $k$-colouring number
$\mathrm{wcol}_{k}(G)$_ of a graph $G$ are defined as follows:

$\displaystyle\mathrm{col}_{k}(G)$ $\displaystyle=1+\min_{L}\max_{y\in
V}|R_{L,k}(y)|,$ $\displaystyle\mathrm{wcol}_{k}(G)$
$\displaystyle=1+\min_{L}\max_{y\in V}|Q_{L,k}(y)|.$

If we allow paths of any length (but still have restrictions on the position
of the internal vertices), we get $R_{L,\infty}(y)$, $Q_{L,\infty}(y)$, the
_$\infty$ -colouring number $\mathrm{col}_{\infty}(G)$_ and the _weak
$\infty$-colouring number $\mathrm{wcol}_{\infty}(G)$_.

We now state the main results of this paper.

######  Theorem 1.6.

(a)For every odd positive integer $p$ and every graph $G$ we have
$\chi(G^{[\natural p]})\leq\mathrm{wcol}_{2p-1}(G)$.

(b)For every even positive integer $p$ and every graph $G$ we have
$\chi(G^{[\natural p]})\leq\mathrm{wcol}_{2p}(G)\cdot\Delta(G)$.

######  Theorem 1.7.

Let $p$ be an odd positive integer and $G$ a graph. Set
$q=\mathrm{wcol}_{p}(G)$.

(a)We have $\chi(G^{[\natural
p]})\leq\bigl{(}\bigl{\lfloor}\frac{1}{2}p\bigr{\rfloor}+2\bigr{)}^{q}$.

(b)If $G$ has odd girth at least $p+1$, then $\chi(G^{\natural
p})\leq\bigl{(}\bigl{\lfloor}\frac{1}{2}p\bigr{\rfloor}+2\bigr{)}^{q}$.

An interesting aspect of generalised colouring numbers is that these
invariants can also be seen as gradations between the colouring number
$\mathrm{col}(G)$ and two important minor monotone invariants, namely the
_tree-width $\mathrm{tw}(G)$_ and the _tree-depth $\mathrm{td}(G)$_ (which is
the minimum height of a depth-first search tree for a supergraph of $G$, see
[18]). More explicitly, for every graph $G$ we have the following relations.

######  Proposition 1.8.

(a)$\mathrm{col}(G)=\mathrm{col}_{1}(G)\leq\mathrm{col}_{2}(G)\leq\dots\leq\mathrm{col}_{\infty}(G)=\mathrm{tw}(G)+1$;

(b)$\mathrm{col}(G)=\mathrm{wcol}_{1}(G)\leq\mathrm{wcol}_{2}(G)\leq\dots\leq\mathrm{wcol}_{\infty}(G)=\mathrm{td}(G)$.

The equality $\mathrm{col}_{\infty}(G)=\mathrm{tw}(G)+1$ was first proved in
[5]. The equality $\mathrm{wcol}_{\infty}(G)=\mathrm{td}(G)$ is [20, Lemma
6.5].

Relations between the two sets of numbers exist as well. Clearly,
$\mathrm{col}_{1}(G)=\mathrm{wcol}_{1}(G)$ and
$\mathrm{col}_{k}(G)\leq\mathrm{wcol}_{k}(G)$. For the converse, Kierstead and
Yang [12] proved that $\mathrm{wcol}_{k}(G)\leq(\mathrm{col}_{k}(G))^{k}$.
Note that this means that if one of the generalised colouring numbers is
bounded for a class of graphs (for some $k$), then so is the other one.

Shortly after Nešetřil and Ossona de Mendez [19] introduced the notion of
_classes with bounded expansion_ , Zhu provided, in [26], a way of
characterising these classes in terms of the weak $k$-colouring numbers. We
will use this characterisation as a definition.

######  Definition 1.9.

A class of graphs $\mathcal{K}$ has _bounded expansion_ if and only if there
exist constants $c_{k}$, $k=1,2,\ldots$ such that $\mathrm{wcol}_{k}(G)\leq
c_{k}$ for all $k$ and all $G\in\mathcal{K}$.

By this definition, Theorem 1.3 (a) follows directly from both Theorems 1.6
(a) and 1.7 (a).

We give the proofs of Theorems 1.6 and 1.7 in the next section. The proof of
Theorem 1.7 actually proves a stronger result. For two graphs $G=(V,E)$ and
$G^{\prime}=(V,E^{\prime})$ on the same vertex set, define $G\cup
G^{\prime}=(V,E\cup E^{\prime})$. Then the upper bound in both parts of
Theorem 1.7 holds for $\chi(G^{[\natural 1]}\cup G^{[\natural
3]}\cup\cdots\cup G^{[\natural p]})$ and $\chi(G^{\natural 1}\cup G^{\natural
3}\cup\cdots\cup G^{\natural p})$, respectively.

A natural question is if for even $p$ we can generalise the bound in Theorem
1.6 (b) by a similar bound $\chi(G^{\natural 2}\cup G^{\natural
4}\cup\cdots\cup G^{\natural p})\leq C\cdot\Delta(G)$, where $C$ depends on
the generalised colouring numbers. But this is not possible. Let
$T_{\Delta,2}$ be the $\Delta$-regular tree of radius 2. Then we have
$\mathrm{wcol}_{1}(T_{\Delta,2})=1$ and $\mathrm{wcol}_{k}(T_{\Delta,2})=2$
for all $k\geq 2$. It is easy to check that $\chi(T_{\Delta,2}^{\natural
2})=\chi(T_{\Delta,2}^{\natural 4})=\Delta$, but $\chi(T_{\Delta,2}^{\natural
2}\cup T_{\Delta,2}{4}^{\natural)}=\Delta(\Delta-1)+1$. These examples
generalise to larger distances.

The results in Theorem 1.7 are best possible in the sense that they give upper
bounds of $\chi(G^{[\natural p]})$ and $\chi(G^{\natural p})$ that depend on
$\mathrm{wcol}_{p}(G)$ only, whereas no such results are possible that depend
on $\mathrm{wcol}_{k}(G)$ with $k<p$. To see this, for $n,p\geq 2$ let
$S_{n,p}$ be the $(p-1)$-subdivision of the complete graph $K_{n}$ (that is,
the graph formed by replacing the edges of $K_{n}$ by paths of length $p$).
Then we obviously have $\chi(S_{n,p}^{[\natural p]})=n$. On the other hand we
have $\mathrm{wcol}_{p-1}(S_{n,p})\leq p+1$. To verify this, order the
vertices of $S_{n,p}$ as follows. First order the branch vertices (the
vertices in the original clique), and then order the subdivision vertices in
any way. Clearly, each branch vertex will not weakly $(p-1)$-access any other
vertex. An internal vertex of a subdivided edge can only weakly $(p-1)$-access
the other $p$ vertices on the path that replaced the edge (including the two
end-vertices of the path). So for fixed odd $p\geq 3$ we cannot bound
$\chi(S_{n,p}^{[\natural p]})$ by an expression that involves
$\mathrm{wcol}_{p-1}(S_{n,p})$ only.

The bound on the odd girth in Theorem 1.7 (b) is also best possible. To show
this, for $k,p\geq 1$ let $A_{k,p}$ be formed by taking the path $P_{p-1}$ of
length $p-2$, and adding $k$ new vertices that are adjacent to both end-
vertices of $P_{p-1}$ only. It is clear that if $p$ is odd, then $A_{k,p}$ has
odd girth $p$. Since between any of the $k$ extra vertices there is a path of
length $p$, we have $\chi(A_{k,p}^{\natural p})\geq k$. The ordering obtained
by taking the two end-vertices of $P_{p-1}$ first, and then ordering the other
vertices in any way, shows that $\mathrm{wcol}_{p}(A_{k,p})\leq p-1$. So for
fixed odd $p\geq 3$ we cannot bound $\chi(A_{k,p}^{\natural p})$ by an
expression that involves $\mathrm{wcol}_{p}(A_{k,p})$ only.

Nešetřil and Ossona de Mendez [20, Section 11.9.3] give examples that even if
we replace “there exists a path of length $p$ between $x$ and $y$” by “there
exists an _induced_ path of length $p$ between $x$ and $y$” in the definition
of $G^{\natural p}$, it is not possible to reduce the bound on the odd girth
in Theorem 1.7 (b).

###  1.3 Explicit upper bounds

The upper bounds obtained by Nešetřil and Ossona de Mendez in their proof of
Theorem 1.3 (a) are very large, even for $p=3$. Their proof relies on the
concept of _$p$ -centred colourings_ of graphs. A (proper) colouring of a
graph $G$ is a _$p$ -centred colouring_ if for each connected induced subgraph
$H$ of $G$, either one colour appears exactly once on $H$ or $H$ gets at least
$p$ colours. This is what is proved in [20].

######  Theorem 1.10 (Nešetřil & Ossona de Mendez [20]).

Let $p$ be an odd positive integer. If a graph $G$ has a $p$-centred colouring
that uses at most $N=N(p)$ colours, then $\chi(G^{[\natural p]})\leq
N2^{N2^{N}}$.

Given a graph $G$, the _star chromatic number_ $\chi_{s}(G)$ is the smallest
number of colours needed to properly colour $G$ such that every two colours
induce a star forest (a forest where every component is isomorphic to a _star
$K_{1,m}$_). It is easy to see that a colouring of a graph is 3-centred if and
only if every two colours induce a star forest. Albertson et al. [3] showed
that the star chromatic number of planar graphs is at most 20, and there exist
planar graphs with star chromatic number equal to 10. This means that the best
known upper bound on $\chi(G^{[\natural 3]})$ for planar graphs given by
Theorem 1.10 is $5\cdot 2^{20,971,522}$, while the best possible upper bound
for planar graphs that can be found using that theorem directly is $5\cdot
2^{10,241}$.

An alternative bound can be obtained from Theorem 1.10 using the following
result.

######  Theorem 1.11 (Zhu [26]).

Every graph $G$ has a $p$-centred colouring that uses at most
$\mathrm{wcol}_{2^{p-2}}(G)$ colours.

######  Corollary 1.12.

Let $p$ be an odd positive integer and $G$ a graph. Setting
$W=\mathrm{wcol}_{2^{p-2}}(G)$ we have $\chi(G^{[\natural p]})\leq
W2^{W2^{W}}$.

As far as we are aware, the best known upper bound for $\mathrm{wcol}_{2}(G)$
for planar is given by the following result.

######  Theorem 1.13 (Van den Heuvel et al. [7]).

For every positive integer $k$ and planar graph $G$ we have
$\displaystyle\mathrm{wcol}_{k}(G)\leq\binom{k+2}{2}\cdot(2k+1)$.

So we have $\mathrm{wcol}_{2}(G)\leq 30$ for planar graphs, which, when
combined with Corollary 1.12, unfortunately gives a worse bound for
$\chi(G^{[\natural 3]})$ for planar graphs than the one obtained earlier.

On the other hand, combining Theorems 1.6 (a) and 1.13 already gives the
significantly better upper bound $\chi(G^{[\natural 3]})\leq 231$ for planar
graphs. In Section 3 we will show that this bound can be lowered further to
143.

The remainder of this paper is organised as follows. In the next section we
prove our main results, Theorems 1.6 and 1.7. We use the results from that
section in Section 3 to find explicit upper bounds for the chromatic number of
exact distance graphs for some specific classes of graphs, including graphs
with bounded genus, graphs with bounded tree-width, and graphs without a
specified complete minor. In Section 4 we describe the graph promised in
Theorem 1.5 (b). We close with a number of open problems and directions for
further study.

##  2 Proofs of the main results

We need a few more definitions. For a positive integer $k$, we denote
$[k]=\\{1,2,\dots,k\\}$. For a vertex $v\in V$, we will denote by $N^{k}(y)$
the _$k$ -th neighbourhood_ of $y$, that is, the set of vertices different
from $v$ with distance at most $k$ from $v$; and we set
$N^{k}[v]=N^{k}(v)\cup\\{v\\}$. As is standard, we write $N(v)$ for
$N^{1}(v)$.

###  2.1 Proof of Theorem 1.6

For later use, we actually prove a slightly stronger result, which involves a
more technical variant of the generalised colouring numbers. Let $G=(V,E)$ be
a graph, $L$ a linear ordering of $V$, and $k$ a positive integer. For a
vertex $y\in V$, let $D_{L,k}(y)$ be the set of vertices $x$ such that there
is a $x,y$-path $P_{x}=z_{0},\dots,z_{s}$, with $x=z_{0}$, $y=z_{s}$, of
length $s\leq k$, such that $x$ is the minimum vertex in $P_{x}$ with respect
to $L$, and such that $y\leq_{L}z_{i}$ for
$\bigl{\lfloor}\frac{1}{2}k\bigr{\rfloor}+1\leq i\leq s$. We define the
_distance- $k$-colouring number $\mathrm{dcol}_{k}(G)$_ of a graph $G$ as
follows:

$\mathrm{dcol}_{k}(G)=1+\min_{L}\max_{y\in V}|D_{L,k}(y)|.$

Since $R_{L,k}(y)\subseteq D_{L,k}(y)\subseteq Q_{L,k}(y)$ for every ordering
$L$, distance $k$ and vertex $y$, we obtain
$\mathrm{col}_{k}(G)\leq\mathrm{dcol}_{k}(G)\leq\mathrm{wcol}_{k}(G)$. On the
other hand, we also have $Q_{L,\lfloor k/2\rfloor+1}(y)\subseteq D_{L,k}(y)$,
which implies that $\mathrm{wcol}_{\lfloor
k/2\rfloor+1}(G)\leq\mathrm{dcol}_{k}(G)$.

We will prove the following sharpening of Theorem 1.6.

######  Theorem 2.1.

(a)For every odd positive integer $p$ and every graph $G$ we have
$\chi(G^{[\natural p]})\leq\mathrm{dcol}_{2p-1}(G)$.

(b)For every even positive integer $p$ and every graph $G$ we have
$\chi(G^{[\natural p]})\leq\mathrm{dcol}_{2p}(G)\cdot\Delta(G)$.

###### Proof.

(a) For an odd positive integer $p$ and graph $G=(V,E)$, set
$q=\mathrm{dcol}_{2p-1}(G)$ and let $L$ be an ordering of $V$ that witnesses
$\max\limits_{y\in V}|D_{L,2p-1}(y)|=q-1$. Moving along the ordering $L$ we
assign to each vertex $y\in V$ a colour $a(y)\in[q]$ that is different from
$a(x)$ for all $x\in D_{L,2p-1}(y)$. Next, define $\mu(y)$ as the minimum
vertex with respect to $L$ of the vertices in $N^{\lfloor p/2\rfloor}[y]$, and
define $h:V\to[q]$ by $h(y)=a(\mu(y))$. We claim that $h$ is a $q$-colouring
of $G^{[\natural p]}$.

Consider an edge $uv\in E(G^{[\natural p]})$. So there exists a path
$P=z_{0},z_{1},\dots,z_{p}$ with $z_{0}=u$ and $z_{p}=v$. Clearly, $N^{\lfloor
p/2\rfloor}[u]\cap N^{\lfloor p/2\rfloor}[v]=\varnothing$, and hence
$\mu(x)\neq\mu(y)$. Without loss of generality, assume $\mu(u)<_{L}\mu(v)$.
Since $\mu(u),z_{\lfloor p/2\rfloor}\in N^{\lfloor p/2\rfloor}[u]$, there
exists a path $S_{1}$ between $\mu(u)$ and $z_{\lfloor p/2\rfloor}$ of length
at most $2\bigl{\lfloor}\frac{1}{2}p\bigr{\rfloor}=p-1$ such that
$V(S_{1})\subseteq N^{\lfloor p/2\rfloor}[u]$. Similarly, there exists a path
$S_{2}$ between $z_{\lfloor p/2\rfloor+1}$ and $\mu(v)$ of length at most
$p-1$ such that $V(S_{2})\subseteq N^{\lfloor p/2\rfloor}[v]$. Since
$N^{\lfloor p/2\rfloor}[u]\cap N^{\lfloor p/2\rfloor}[v]=\varnothing$ and
$z_{\lfloor p/2\rfloor}z_{\lfloor p/2\rfloor+1}\in E$, we can combine these
paths to a path $S$ between $\mu(u)$ and $\mu(v)$ of length at most $2p-1$.

Note that if we write $S=w_{0},w_{1},\ldots,w_{t}$ with $w_{0}=\mu(u)$ and
$w_{t}=\mu(v)$, then the vertices $w_{i}$ for
$\bigl{\lfloor}\frac{1}{2}k\bigr{\rfloor}+1\leq i\leq t$ all lie on $S_{2}$,
hence are in $N^{\lfloor p/2\rfloor}[v]$. Since $\mu(v)$ is the minimum vertex
in $N^{\lfloor p/2\rfloor}[v]$, we have $\mu(v)\leq_{L}w_{i}$ for those
$w_{i}$. Thus $S$ witnesses that $\mu(u)\in D_{L,2p-1}(\mu(v))$. We conclude
that $h(u)=a(\mu(u))\neq a(\mu(v))=h(v)$, as required.

(b) For an even positive integer $p$ and graph $G=(V,E)$, set
$q=\mathrm{dcol}_{2p}(G)$ and let $L$ be an ordering of $V$ that witnesses
$\max\limits_{y\in V}|D_{L,2p}(y)|=q-1$. Moving along the ordering $L$ we
assign to each vertex $y\in V$ a colour $a(y)\in[q]$ that is different from
$a(x)$ for all $x\in D_{L,2p}(y)$. Additionally, for each vertex $y$, choose
an injective function $c_{y}:N(y)\to[\Delta(G)]$.

Next, define $\mu(y)$ as the minimum vertex with respect to $L$ of the
vertices in $N^{p/2}[y]$. We also choose an arbitrary vertex in $N(\mu(y))\cap
N^{p/2-1}(y)$; call it $\beta(y)$. To each vertex $y$ we assign as its colour
the pair $(a(\mu(y)),c_{\mu(y)}(\beta(y))$. It is clear that this colouring
uses at most $q\cdot\Delta(G)$ colours, and we claim that it is a proper
colouring of $G^{[\natural p]}$.

Consider an edge $uv\in E(G^{[\natural p]})$. First suppose that
$\mu(u)\neq\mu(v)$. Then we can follow the proof of part (a) to conclude that
$a(\mu(u))\neq a(\mu(v))$, and hence the colours of $u$ and $v$ differ in the
first coordinate.

So we are left with the case $\mu(u)=\mu(v)$. Since $d_{G}(u,v)=p$, we have
that $\mu(v)\in N^{p/2}(u)\cap N^{p/2}(v)$, while $N^{p/2-1}(u)\cap
N^{p/2-1}(v)=\varnothing$. This means that $\beta(u)\neq\beta(v)$. Together
with the fact that $\beta(u),\beta(v)\in N(\mu(v))$, we obtain that
$c_{\mu(v)}(\beta(u))\neq c_{\mu(v)}(\beta(v))$. This gives that the colours
of $u$ and $v$ differ in the second coordinate, which completes the proof. ∎

###  2.2 Proof of Theorem 1.7

In the proof of Theorem 1.7 we use the following lemmas.

######  Lemma 2.2.

Let $G$ be a graph and $L$ a linear ordering of $V$. Let $x,y,z$ be distinct
vertices in $G$. If $x$ is weakly $k$-accessible from $y$, and $z$ is weakly
$\ell$-accessible from $y$, then $x$ is weakly $(k+\ell)$-accessible from $z$
or $z$ is weakly $(k+\ell)$-accessible from $x$.

###### Proof.

Since $x$ is weakly $k$-accessible from $y$, there is a path
$x,v_{1},v_{2},\ldots,v_{r-1},y$ of length $r\leq k$ for which all internal
vertices $v_{i}$ satisfy $x<_{L}v_{i}$. Also, since $z$ is weakly
$\ell$-accessible from $y$, there is a path $y,u_{1},u_{2},\ldots,u_{s-1},z$
of length $s\leq\ell$ for which all internal vertices $u_{j}$ satisfy
$z<_{L}u_{j}$. Then, if $x<_{L}z$, there is an $x,z$-path of length at most
$k+\ell$ with all internal vertices greater than $x$ in $L$; hence, $x$ is
weakly $(k+\ell)$-accessible from $z$. Similarly, if $z<_{L}x$, then $z$ is
weakly $(k+\ell)$-accessible from $x$. ∎

######  Lemma 2.3.

Let $p$ be a positive integer and $G$ a graph with odd girth at least $p+1$

(a)Every closed walk of odd length has length at least $p+1$.

(b)Let $x,y$ be different vertices and $W$ a walk between $x$ and $y$ of
length $r\leq p$. Then there exists a path between $x$ and $y$ of length
$s\leq r$ such that $s$ and $r$ have the same parity.

###### Proof.

The proof of (a) is straightforward, since a closed walk of odd length
contains a cycle of odd length. For (b), let $W=w_{0},\ldots,w_{r}$, with
$x=w_{0}$ and $y=w_{r}$. If $W$ itself is not a path, then some vertex $z$
appears more than once in $W$. The part of $W$ between the first and last
appearances of $z$ is a closed walk $W^{\prime}$ of length $t\leq r$. Using
(a) we obtain that $t$ must be even. Hence, if we remove $W^{\prime}$ from
$W$, we get a shorter walk between $x$ and $y$ of length $r-t\equiv
r\pmod{2}$. Additionally, the resulting walk has fewer vertices that appear
more than once than $W$ does. Hence, if we do not immediately obtain a path,
we can repeat this procedure inductively until we obtain an $xy$-path with the
desired property. ∎

###### Proof of Theorem 1.7.

For both parts of the theorem we use the same colouring. Let $L$ be an
ordering of $V$ such that $\max\limits_{y\in V}|Q_{L,p}(y)|=q-1$. We first
create an auxiliary colouring $a(y)\in[q]$ by moving along the ordering $L$,
and assigning to each vertex $y\in V$ a colour $a(y)\in[q]$ that is different
from $a(x)$ for all $x\in Q_{L,p}(y)$. Next, for a vertex $x\in Q_{L,\lfloor
p/2\rfloor}(y)$, let $d_{y}^{\prime}(x)$ be the minimum integer $k$ such that
$x$ is weakly $k$-accessible from $y$, and set $d_{y}^{\prime}(y)=0$.

Define the function
$b_{y}:[q]\rightarrow\bigl{[}\bigl{\lfloor}\frac{1}{2}p\bigr{\rfloor}\bigr{]}\cup\\{-1,0\\}$
as follows. For a colour $c\in[q]$, let

$b_{y}(c)=\left\\{\begin{array}[]{rl}d_{y}^{\prime}(x),&\text{if there exists
an $x\in Q_{L,\lfloor p/2\rfloor}(y)\cup\\{y\\}$ with
$a(x)=c$};\\\\[2.84526pt] -1,&\text{otherwise}.\end{array}\right.$

By Lemma 2.2 and the definition of $a(x)$, we see that if $x\in Q_{L,\lfloor
p/2\rfloor}(y)\cup\\{y\\}$ satisfies $a(x)=c$, then $x$ is the only vertex in
$Q_{L,\lfloor p/2\rfloor}(y)\cup\\{y\\}$ with colour $c$. That implies that
$b_{y}$ is well defined.

The number of possible functions
$b_{y}:[q]\rightarrow\bigl{[}\bigl{\lfloor}\frac{1}{2}p\bigr{\rfloor}\bigr{]}\cup\\{-1,0\\}$
is $\bigl{(}\bigl{\lfloor}\frac{1}{2}p\bigr{\rfloor}+2\bigr{)}^{q}$. We will
prove that labelling each vertex $y\in V$ with $b_{y}$ gives a proper
colouring for the graphs and situations described in parts (a) and (b) of the
theorem. It is more convenient to do part (b) first.

(b) Consider two vertices $u,v$ for which there exists a path of length $p$
between $u$ and $v$. Without loss of generality we assume $u<_{L}v$. If $u$ is
weakly $p$-accessible from $v$ in $L$, then we know that $a(u)\neq a(v)$, and
hence $b_{u}(a(u))=0\neq b_{v}(a(u))$.

So we are left with the case in which $u$ is not weakly $p$-accessible from
$v$ in $L$. Let $k$ be the length of the shortest odd-length path between $u$
and $v$. We obviously have $k\leq p$. Because $u$ is not weakly $p$-accessible
from $v$ in $L$, we also have $k\neq 1$, hence $k\geq 3$. Let
$P=z_{0},z_{1},z_{2},\ldots,z_{k-1},z_{k}$ be a path of length $k$ between
$u=z_{0}$ an $v=z_{k}$. Let $z_{\ell}$ be the vertex of $P$ that is minimum
with respect to the ordering $L$. Since $u<_{L}v$, we get that $z_{\ell}\neq
v$, and, since $u$ is not weakly $p$-accessible from $v$, we see that
$z_{\ell}\neq u$. Therefore, $z_{\ell}$ is weakly $l$-accessible from $u$ and
weakly $(k-\ell)$-accessible from $v$.

First consider the case that $\ell<k-\ell$. Then $\ell<\frac{1}{2}k$. We want
to prove that $d^{\prime}_{u}(z_{\ell})=\ell$. For this, assume that
$d^{\prime}_{u}(z_{\ell})=m<\ell$. Hence there is a path $A$ between $u$ and
$z_{\ell}$ of length $m$. If $\ell$ and $m$ have different parity, then the
union of $A$ and the path $z_{0},z_{1},\ldots,z_{\ell}$ gives a closed walk of
odd length $m+\ell<2\ell<k\leq p$, which contradicts Lemma 2.3 (a). So $m$ and
$\ell$ have the same parity. Now if we replace in the path $P$ the part
$z_{0},z_{1},\ldots,z_{\ell}$ with $A$, we get a walk between $u$ and $v$ of
length $k-\ell+m<k$, hence with odd length. By Lemma 2.3 (b), this walk
contains a path between $u$ and $v$ of odd length at most $k-\ell+m<k$, which
contradicts the choice of $P$.

So we know that $d^{\prime}_{u}(z_{\ell})=\ell$. Notice that since there is a
path of length $k-\ell$ between $z_{\ell}$ and $v$, we have that
$d^{\prime}_{v}(z_{\ell})\leq k-\ell\leq p-\ell$. Since
$\ell<\frac{1}{2}k\leq\frac{1}{2}p$, we have that $z_{\ell}\in Q_{L,\lfloor
p/2\rfloor}(u)$, and hence $b_{u}(a(z_{\ell}))=\ell$.

Now consider a vertex $x\in Q_{L,\lfloor p/2\rfloor}(v)$ with
$d_{v}^{\prime}(x)=\ell$. We first prove that $x\neq z_{\ell}$. For suppose
this is not the case, then there is a path from $v$ to $z_{\ell}$ of length
$\ell$. Together with the part of $z_{\ell},z_{\ell+1},\ldots,z_{k}=v$ from
the path $P$, this gives a closed walk of length $k\leq p$. Since $k$ is odd,
this contradicts Lemma 2.3 (a).

Since $d^{\prime}_{v}(x)=\ell$, $d_{v}^{\prime}(z_{\ell})\leq p-\ell$ and
$x\neq z_{\ell}$, by Lemma 2.2 we get that $x$ is weakly $p$-accessible from
$z_{\ell}$ or $z_{\ell}$ is weakly $p$-accessible from $x$. This gives
$a(x)\neq a(z_{\ell})$, which implies, by choice of $x$, that
$b_{v}(a(z_{\ell}))\neq\ell$.

If $k-\ell<\ell$, we can prove in a similar way that $b_{u}\neq b_{v}$, which
completes the proof of part (b) of the theorem.

(a) This time we consider two vertices $u,v$ that have distance $k$ in $G$,
for some odd integer $k\leq p$. (To prove the statement, it would be enough to
prove the case $k=p$, but we prefer to give the proof of a more general
statement.) We can more or less follow the proof of part (b) above, working
with a shortest path $P=z_{0},z_{1},z_{2},\ldots,z_{k-1},z_{k}$ between
$u=z_{0}$ and $v=z_{k}$.

Since $P$ is a shortest path, we immediately get that
$d_{u}^{\prime}(z_{\ell})=d_{G}(u,z_{\ell})=\ell$ and
$d_{v}^{\prime}(z_{\ell})=d_{G}(v,z_{\ell})=p-\ell$. This also means that
$x\neq z_{\ell}$, since $d_{G}(v,x)\leq d_{v}^{\prime}(x)=\ell<p-\ell$. For
the remainder, the proofs are exactly the same. ∎

The proofs of Theorem 1.7 (a) and (b) above give results that are stronger
than the statements in the theorem. We already discussed in Subsection 1.2
that in fact we prove upper bounds on $\chi(G^{[\natural 1]}\cup G^{[\natural
3]}\cup\cdots\cup G^{[\natural p]})$ and $\chi(G^{\natural 1}\cup G^{\natural
3}\cup\cdots\cup G^{\natural p})$. Additionally, in part (a) we could replace
the condition that we add an edge $uv$ to $G^{[\natural p]}$ if
$d_{G}(u,v)=p$, i.e. “there is a shortest path of length $p$ between $u$ and
$v$”, by the weaker condition “there is a path $P$ of length $p$ between $u$
and $v$ such that any shorter path between those vertices is internally
disjoint from $P$”.

##  3 Explicit upper bounds on the chromatic number of exact distance graphs

In this section we use Theorem 2.1 (a) to find explicit upper bounds for the
chromatic number of exact distance graphs for certain types of graphs,
including planar graphs, graphs with bounded tree-width, and graphs without a
complete minor. Obtaining these bounds involves finding upper bounds for the
distance-$k$-colouring numbers $\mathrm{dcol}_{k}(G)$. More explicitly, we
will prove the following results.

######  Theorem 3.1.

Let $k$ be a positive integer.

(a)For every planar graph $G$ we have
$\displaystyle\mathrm{dcol}_{k}(G)\leq\Bigl{(}2\binom{\lfloor
k/2\rfloor+2}{2}+1\Bigr{)}\cdot(2k+1)$.

(b)For every graph $G$ with genus $g$ we have
$\displaystyle\mathrm{dcol}_{k}(G)\leq\Bigl{(}2g+2\binom{\lfloor
k/2\rfloor+2}{2}+1\Bigr{)}\cdot(2k+1)$.

######  Theorem 3.2.

Let $k$ and $t$ be positive integers. For every graph $G$ with tree-width at
most $t$ we have $\displaystyle\mathrm{dcol}_{k}(G)\leq t\cdot\binom{\lfloor
k/2\rfloor+t}{t}+1$.

######  Theorem 3.3.

Let $k$ and $t$ be positive integers with $t\geq 4$. For every $K_{t}$-minor
free graph $G$ we have
$\displaystyle\mathrm{dcol}_{k}(G)\leq\Bigl{(}(t-2)\binom{\lfloor
k/2\rfloor+t-2}{t-2}+1\Bigr{)}\cdot(t-3)(2k+1)$.

Since outerplanar graphs $G$ have tree-width at most 2, combining Theorems 2.1
(a) and 3.2 gives $\chi(G^{[\natural 3]})\leq 13$. Similarly, from Theorem 3.1
we see that for planar graphs $G$ we have $\chi(G^{[\natural 3]})\leq 143$,
while for graphs $G$ embeddable on the torus we have $\chi(G^{[\natural
3]})\leq 165$.

We will prove those theorems in the remainder of this section. They are based
on the methods developed in Van den Heuvel et al. [7] to obtain bounds for the
generalised colouring numbers.

###  3.1 Graphs with bounded tree-width

Proposition 1.8 tells us that $\mathrm{col}_{\infty}(G)=\mathrm{tw}(G)+1$. In
[5], Grohe et al. provided a sharp upper bound for the weak colouring numbers
$\mathrm{wcol}_{k}(G)$ of a graph $G$ in terms of its tree-width. The
following result is implicit in the proof of [5, Theorem 4.2].

######  Lemma 3.4 (Grohe et al. [5]).

Let $G$ be a graph and $L$ a linear ordering of $V(G)$ with $\max\limits_{y\in
V(G)}|R_{L,\infty}(y)|\leq t$. For every positive integer $k$ and vertex $y\in
V(G)$ we have $\displaystyle|Q_{L,k}(y)|\leq\binom{k+t}{t}-1$.

###### Proof of Theorem 3.2..

Since $G$ has tree-width at most $t$, we have $\mathrm{col}_{\infty}(G)\leq
t+1$, and so there is an ordering $L$ of $V(G)$ such that $\max\limits_{y\in
V(G)}|R_{L,\infty}(y)|\leq t$. By Lemma 3.4 we get that for every positive $k$
and $y\in V(G)$ we have $|Q_{L,k}(y)|\leq\binom{k+t}{t}-1$. Consider $v\in
V(G)$, and for each $u\in D_{L,k}(v)$ fix a path $P_{u}=z_{s},\dots,z_{0}$
with $s\leq k$, $v=z_{s}$, $u=z_{0}$, such that $u$ is minimum on $P_{u}$, and
such that $\sigma(u)$, which denotes the greatest index with
$z_{\sigma(u)}<_{L}v$, satisfies
$0\leq\sigma(u)\leq\bigl{\lfloor}\frac{1}{2}k\bigr{\rfloor}$. Such a path
exists by the definition of $D_{L,k}(v)$. It is clear that subpaths of $P_{u}$
give that $z_{\sigma(u)}$ is $(s-\sigma(u))$-accessible from $v$ and $u$ is
weakly $\sigma(u)$-accessible from $z_{\sigma(u)}$. Since $s\leq k$ and
$0\leq\sigma(u)\leq\bigl{\lfloor}\frac{1}{2}k\bigr{\rfloor}$, we obtain that
$z_{\sigma(u)}$ is $k$-accessible from $v$ and $u$ is weakly
$\bigl{\lfloor}\frac{1}{2}k\bigr{\rfloor}$-accessible from $z_{\sigma(u)}$.
Together with our choice of $L$, this gives us the following estimates:

$|D_{L,k}(v)|\leq|R_{L,k}(v)|\cdot\bigl{(}|Q_{L,\lfloor
k/2\rfloor}(v)|+1\bigr{)}\leq t\cdot\binom{\lfloor k/2\rfloor+t}{t}.$

The result follows immediately. ∎

###  3.2 Graphs with excluded complete minors

In order to provide upper bounds for the generalised colouring numbers for
graphs that exclude a fixed minor, Van den Heuvel et al. [7] constructed
vertex partitions where each part has neighbours in a bounded number of other
parts only, and where the intersection of each part with the $k$-neighbourhood
of any vertex is also bounded. We will make use of these decompositions for
our proofs as well.

A _decomposition_ of a graph $G$ is a sequence
$\mathcal{H}=(H_{1},\ldots,H_{\ell})$ of non-empty subgraphs of $G$ such that
the vertex sets $V(H_{1}),\ldots,V(H_{\ell})$ partition $V(G)$. The
decomposition $\mathcal{H}$ is _connected_ if each $H_{i}$ is connected.

Let $\mathcal{H}=(H_{1},\ldots,H_{\ell})$ be a decomposition of a graph $G$,
$i$ a positive integer, and $C$ a component of $G-\bigcup_{1\leq j\leq
i}V(H_{j})$. We define the _$i$ -th separating number of $C$_ as
$s_{i}(C)=|\\{j\in[i]\mid E(C,H_{j})\neq\varnothing\\}|$, where $E(C,H_{j})$
is the set of edges with one end-vertex in $C$ and the other end-vertex in
$H_{j}$. Let $w_{i}(\mathcal{H})=\max s_{i}(C)$, where the maximum is taken
over all components $C$ of $G-\bigcup_{1\leq j<i}V(H_{j})$. We define the
_width_ of $\mathcal{H}$ as $W(\mathcal{H})=\max\limits_{1\leq
i\leq\ell}w_{i}(\mathcal{H})$.

Let $G$ be a graph, let $H\subseteq G$ be a _connected_ subgraph of $G$, and
let $f:\mathbb{N}\to\mathbb{N}$ be a function. We say that $H$ _$f$ -spreads
on $G$_ if, for every $k\in\mathbb{N}$ and $v\in V(G)$, we have

$|N^{k}[v]\cap V(H)|\leq f(k).$

We say a decomposition $\mathcal{H}$ is _$f$ -flat_ if each $H_{i}$
$f$-spreads on $G-\bigcup_{1\leq j<i}V(H_{j})$. We say $\mathcal{H}$ is a
_flat decomposition_ if $\mathcal{H}$ is an $f$-flat decomposition for some
function $f:\mathbb{N}\to\mathbb{N}$.

Van den Heuvel et al. [7] related the width of a connected decomposition to
the tree-width of the minor obtained by contracting each part.

######  Lemma 3.5 (Van den Heuvel et al. [7]).

Let $G$ be a graph, and let $\mathcal{H}=(H_{1},\dots,H_{\ell})$ be a
connected decomposition of $G$ of width at most $t$. By contracting each
(connected) subgraph $H_{i}$ to a single vertex, we obtain a graph $H$ with
$\ell$ vertices and tree-width at most $t$.

The proof of the lemma in [7] shows the power of generalised colouring
numbers. It actually gives a short argument that the contracted graph $H$
satisfies $\mathrm{col}_{\infty}(H)\leq t+1$. The bound on the tree-width then
follows by Proposition 1.8. Moreover, the proof shows that the ordering $L$ of
$V(H)$ obtained by setting $H_{i}<_{L}H_{j}$ if $i<j$ satisfies
$\max\limits_{1\leq i\leq\ell}|R_{L,\infty}(H_{i})|\leq t$. Using this
property we can prove that if the decomposition from which $H$ was obtained is
$f$-flat, then we can find an upper bound on $\mathrm{dcol}_{k}(G)$ in terms
of $f(k)$.

######  Lemma 3.6.

Let $f:\mathbb{N}\to\mathbb{N}$ and let $t,k$ be positive integers. For every
graph $G$ that admits a connected $f$-flat decomposition of width at most $t$
we have $\displaystyle\mathrm{dcol}_{k}(G)\leq\Bigl{(}t\cdot\binom{\lfloor
k/2\rfloor+t}{t}+1\Bigr{)}\cdot f(k)$.

###### Proof.

The proof of this lemma is similar to that of [7, Lemma 3.5]. Let
$\mathcal{H}=(H_{1},\dots,H_{\ell})$ be a connected $f$-flat decomposition of
$G$ of width $t$. Since $\mathcal{H}$ is connected, we know, by Lemma 3.5,
that contracting the subgraphs in $\mathcal{H}$ leads to a graph $H$ with
tree-width at most $t$. We identify the vertices of $H$ with the subgraphs
$H_{i}$, and define a linear ordering $L$ on $V(H)$ by setting
$H_{i}<_{L}H_{j}$ if $i<j$. By the proof of [7, Lemma 3.1] we get that $L$
satisfies $\max\limits_{1\leq i\leq\ell}|R_{L,\infty}(H_{i})|\leq t$. Using
Lemma 3.4 this implies that $|Q_{L,\lfloor
k/2\rfloor}(H_{i})|\leq\binom{\lfloor k/2\rfloor+t}{t}-1$ for any vertex
$H_{i}\in V(H)$. Arguing as in the proof of Theorem 3.2, this means that for
every $H_{i}\in V(H)$ we have $|D_{L,k}(H_{i})|\leq t\cdot\binom{\lfloor
k/2\rfloor+t}{t}$.

From $L$ we define an ordering $L^{\prime}$ on $V(G)$ in the following way.
For $u\in H_{i}$ and $v\in H_{j}$ with $i\neq j$, we let $u<_{L^{\prime}}v$ if
$i<j$. Then, for every $1\leq i\leq\ell$, we order the vertices of $H_{i}$ in
any order. It is easy to see that any vertex $v\in H_{i}$ satisfies

$D_{L^{\prime},k}(v)\subseteq N^{k}[v]\cap\bigl{(}H_{i}\cup\\{\,H_{j}\mid
H_{j}\in D_{L,k}(H_{i})\,\\}\bigr{)}.$

Hence, we have that there are at most $t\cdot\binom{\lfloor
k/2\rfloor+t}{t}+1$ subgraphs among $H_{1},\ldots,H_{\ell}$ in $G$ that
contain vertices from $D_{L^{\prime},k}(v)$. Since $\mathcal{H}$ is $f$-flat,
we know that the intersection of each of these subgraphs with $N^{k}[v]$ is at
most $f(k)$. Finally, since $D_{L^{\prime},k}(v)$ is a proper subset of
$N^{k}[v]$ (as $v\notin D_{L^{\prime},k}(v)$), the result follows. ∎

Also in [7], it was proved that graphs that do not contain a complete graph as
a minor have flat decompositions of small width.

######  Lemma 3.7 (Van den Heuvel et al. [7]).

Let $t\geq 4$ and let $f:\mathbb{N}\to\mathbb{N}$ be the function
$f(k)=(t-3)(2k+1)$. For every $K_{t}$-minor free graph $G$ we have that there
is a connected $f$-flat decomposition of $G$ with width at most $t-2$.

Combining Lemmas 3.6 and 3.7 immediately gives Theorem 3.3.

Flat decompositions of even smaller width were found in [7] for planar graphs.

######  Lemma 3.8 (Van den Heuvel et al. [7]).

Let $f:\mathbb{N}\to\mathbb{N}$ be the function $f(k)=2k+1$. For every maximal
planar graph $G$ we have that there is a connected $f$-flat decomposition of
$G$ with width at most 2.

This lemma allows us, through Lemma 3.6, to prove Theorem 3.1 (a).

###### Proof of Theorem 3.1 (a).

By combining Lemmas 3.6 and 3.8, we get the bound on $\mathrm{dcol}_{k}(G)$
for maximal planar graphs. Since $\mathrm{dcol}_{k}(G)$ cannot decrease when
edges are added, we conclude that any planar graph satisfies the same
inequality. ∎

We say a path is optimal if it is a shortest path between its end-points. To
prove Theorem 3.1 (b), we use the following easy result which states that a
decomposition in which all subgraphs are optimal paths is $f$-flat for
$f(k)=2k+1$.

######  Lemma 3.9 (Van den Heuvel et al. [7]).

Let $G$ be a graph, $y$ be a vertex of $G$, and $P$ be an optimal path in $G$.
Then $P$ contains at most $2k+1$ vertices of the closed $k$-neighbourhood
$N^{k}[y]$ of $y$.

###### Proof of Theorem 3.1 (b).

The proof of this statement is similar to the proof of [7, Theorem 1.5 (a)].
We assume $g>0$, as otherwise the result holds by Theorem 3.1 (a). It is well
known (see e.g. [17, Lemma 4.2.4] or [22]) that a graph of genus $g>0$
contains a non-separating cycle $C$ that consists of two optimal paths and
such that $G-C$ has genus $g-1$. We construct a linear order $L$ of $V$ in the
following way. The first vertices in $L$ will be the vertices in such a cycle
$C$. If after removing that cycle the genus of the resulting graph is greater
than 0, then we choose another such cycle, make its vertices the next ones in
the ordering, and remove the cycle. We repeat this process inductively until
the resulting graph is a planar graph $G^{\prime}$. The vertices of
$G^{\prime}$ are placed at the end of $L$, ordered in the way the gives the
bound on $\mathrm{dcol}_{k}(G^{\prime})$ from Theorem 3.1 (a).

Lemma 3.9 tells us that for any vertex $y$ and optimal path $P$ we have
$|N^{k}[y]\cap V(P)|\leq 2k+1$ for every $k$. Hence $|D_{L,k}(y)\cap V(P)|\leq
2k+1$ for every vertex $y$ and optimal path $P$. It follows that for any
vertex $y$ in $G$, the set $D_{L,2p-1}(y)$ can have at most $2g(2k+1)$
vertices on the removed cycles. (Each of the two optimal paths that form a
cycle is optimal after the earlier cycles are removed, and vertices cannot
belong to $D_{L,2p-1}(y)$ through vertices in older cycles.) Only a vertex $x$
in the planar graph $G^{\prime}$ can have other vertices of $G^{\prime}$ in
$D_{L,k}(x)$ and Theorem 3.1 (a) gives us a bound on the number of such
vertices. Hence, we obtain that every $y$ in $G$ satisfies

$|D_{L,k}(y)|\leq 2g\cdot(2k+1)+\Bigl{(}2\binom{\lfloor
k/2\rfloor+2}{2}+1\Bigr{)}\cdot(2k+1)-1.$

The result follows. ∎

##  4 A lower bound on the chromatic number of exact distance-3 graphs of
planar graphs

Figure 2:  An outerplanar graph $G_{4}$ with $\chi(G_{4}^{[\natural 3]})=5$.

In [20, Exercise 11.4] a planar graph $G$ such that $\chi(G^{[\natural 3]})=6$
is given (see also [21]). As we will prove below, the outerplanar graph
$G_{4}$ in Figure 2 satisfies $\chi(G_{4}^{[\natural 3]})=5$. We will use that
graph to construct a planar graph $G_{5}$ such that $\chi(G_{5}^{[\natural
3]})=7$.

######  Theorem (Theorem 1.5 (b)).

There is a planar graph $G_{5}$ such that $\chi(G_{5}^{[\natural 3]})=7$.

###### Proof.

We will prove first that $\chi(G_{4}^{[\natural 3]})=5$, using the vertex
labelling provided in Figure 2. Consider a proper colouring of
$G_{4}^{[\natural 3]}$. Note that
$C^{1}=x_{1}^{1},x_{2}^{1},x_{3}^{1},x_{4}^{1},x_{5}^{1},x_{1}^{1}$ and
$C^{2}=x_{1}^{2},x_{2}^{2},x_{3}^{2},x_{4}^{2},x_{5}^{2},x_{1}^{2}$ form
disjoint 5-cycles $G_{4}^{[\natural 3]}$. Hence, the vertices in $V(C^{1})\cup
V(C^{2})$ need at least 3 colours. Given that $V(C^{1})\cup V(C^{2})\subseteq
N(z)$ in $G_{4}^{[\natural 3]}$, if we use more than 3 colours on
$V(C^{1})\cup V(C^{2})$, then we already use at least 5 colours. So assume
that the vertices in $V(C^{1})\cup V(C^{2})$ are coloured with 3 colours only.
Since $V(C^{i})\subseteq N(y^{i})$ in $G_{4}^{[\natural 3]}$ for $i=1,2$, and
$y^{1}y^{2}\in E(G_{4}^{[\natural 3]})$, we need at least 2 extra colours. So
we always use at least 5 colours in a proper colouring of $G_{4}^{[\natural
3]}$. Figure 2 gives a colouring of $G_{4}$ with 5 colours which is a proper
colouring of $G_{4}^{[\natural 3]}$. This shows that $\chi(G_{4}^{[\natural
3]})=5$.

Now let $F_{1}$ and $F_{2}$ be two disjoint copies of $G_{4}$. Let $H$ be a
path on 5 vertices, disjoint from $F_{1}$ and $F_{2}$, with vertices
$y_{1}^{\prime},w_{1}^{\prime},z^{\prime},w_{2}^{\prime},y_{2}^{\prime}$ in
that order, together with the edge $w_{1}^{\prime}w_{2}^{\prime}$. (This is
exactly the graph formed by the vertices $\\{y^{1},w^{1},z,w^{2},y^{2}\\}$ in
Figure 2.) The graph $G^{-}_{5}$ has vertex set and edge set:

$\displaystyle V(G^{-}_{5})$ $\displaystyle=V(F_{1})\cup V(F_{2})\cup V(H);$
$\displaystyle E(G^{-}_{5})$ $\displaystyle=E(F_{1})\cup E(F_{2})\cup
E(H)\cup\\{\,b_{1}w_{1}^{\prime}\mid b_{1}\in
V(F_{1})\,\\}\cup\\{\,b_{2}w_{2}^{\prime}\mid b_{2}\in V(F_{2})\,\\}.$

Finally, the graph $G_{5}$ is obtained from $G^{-}_{5}$ by subdividing once
all the edges of the form $b_{1}w_{1}^{\prime}$ and $b_{2}w_{2}^{\prime}$
(replacing each edge by a path of length 2). Since $G_{4}$ is outerplanar, it
is easy to check that $G_{5}$ is planar.

If $u,v\in V(F_{1})$ and $P$ is an $u,v$-path in $G_{5}$ but $V(P)\nsubseteq
V(F_{1})$, then $w_{1}^{\prime}\in V(P)$. Thus the length of $P$ is at least
4. We conclude that if two vertices $u,v$ have distance 3 in $G_{5}$, then any
shortest $u,v$-path has all its vertices in $V(F_{1})$. Therefore, the number
of colours needed to colour the vertices of $F_{1}$ in $G_{5}^{[\natural 3]}$
is 5, and the same applies to $F_{2}$. We now can argue as in the proof of
$\chi(G_{4}^{[\natural 3]})=5$ above to reach the conclusion
$\chi(G_{5}^{[\natural 3]})=7$. ∎

Since the graph $G_{4}$ in Figure 2 is outerplanar, it does not have $K_{4}$
as a minor. Also, the graph $G_{5}$ we constructed above is planar, so does
not have $K_{5}$ as a minor. We can iterate the construction to obtain graphs
$G_{t}$ that are $K_{t}$-minor free, for $t\geq 4$, and for which
$\chi(G_{t}^{[\natural 3]})\geq 2(t-2)+1$. To obtain $G_{t+1}$ from $G_{t}$,
we take two copies of $G_{t}$, one copy of the graph $H$ from above, and add
paths of length 2 between all vertices in the first copy of $G_{t}$ and
$w_{1}^{\prime}$, and between all vertices in the second copy of $G_{t}$ and
$w_{2}^{\prime}$. It is straightforward to check that if $G_{t}$ is
$K_{t}$-minor free, then $G_{t+1}$ is $K_{t+1}$-minor free, and that
$G_{t+1}^{[\natural 3]}$ needs at least 2 more colours than $G_{t}^{[\natural
3]}$ does.

The property that for $t\geq 5$ there exists graphs $G$ that are $K_{t}$-minor
free and satisfy $\chi(G^{[\natural 3]})\geq 2(t-2)+1$ does not extend to
$t=3$. To see this, note that the only graphs that are $K_{3}$-minor free are
acyclic graphs (i.e. forests), which implies they are bipartite. And for
bipartite graphs $G$ we have that $G^{[\natural 3]}$ is bipartite as well (in
fact, even the exact $p$-power graph $G^{\natural p}$ is bipartite for every
odd $p$), hence $\chi(G^{[\natural 3]})\leq 2$.

Notice that one can construct the graph $G_{4}$ of Figure 2 (and the graphs
$G_{t}$ for $t\geq 4$) by using operations similar to those of used in the
Hajós construction [6]. Consider the graph $S$ induced on $G_{4}$ by
$(N(w^{1})\setminus
w^{2})\cup\\{w_{1},x_{1}^{1},x_{2}^{2},\ldots,x_{5}^{1}\\}$. The main
connected component of the graph $S^{[\natural 3]}$ consists of a cycle and
two apex vertices, $z$ and $y_{1}$, that are adjacent to all the vertices in
the cycle. One can obtain $G_{4}$ by taking two copies of $S$, identifying the
two vertices that correspond to $z$, and adding an edge between the two
vertices that correspond to $w_{1}$. In the exact distance-3 graph, we see
that one of the apex vertices has been identified, while those that correspond
to $y_{1}$ have been joined by an edge. However, the operation of deletion,
used in the Hajós construction, is not used in our construction. This is
mainly because we want to obtain a graph with chromatic number strictly larger
than that of the parts it is formed of.

##  5 Discussion and open problems

In this paper we give bounds on the chromatic number of exact distance graphs
for some classes of graphs. In general, the difference between the best lower
and upper bounds are still quite large, so we can’t really claim we have an
insight of what the correct best possible bounds are.

A second feature of our upper bounds is that they are expressed in terms of
generalised colouring numbers, and hence are increasing with the distance.
However, for none of the classes of graphs do we have examples that show that
$\chi(G^{[\natural p]})$ grows when the odd number $p$ increases. This feature
was noticed earlier for planar graphs. The following problem, which is
attributed to Van den Heuvel and Naserasr, appears in [20] (see also [21]).

######  Problem 5.1 ([20, Problem 11.1]).

Is there a constant $C$ such that for every odd integer $p$ and every planar
graph $G$ we have $\chi(G^{[\natural p]})\leq C$ ?

Of course, the same question can be asked for graph classes with bounded tree-
width and graphs that exclude a complete minor. It is known that for all those
classes the weak $p$-colouring number is not bounded when $p$ increases. Grohe
et al. [5] proved that for every pair of positive integers $k,s$ there is a
graph $G_{k,s}$ of tree-width $s$ such that
$\mathrm{wcol}_{k}(G_{k,s})=\binom{k+s}{s}$. Since graphs of tree-width $s$
are $K_{s+2}$-minor free, for every $t\geq 3$ the graph $G_{k,t-2}$ is
$K_{t}$-minor free and satisfies
$\mathrm{wcol}_{k}(G_{k,t-2})=\binom{k+t-2}{t-2}\in\Omega(k^{t-2})$. Note that
this also means that $\mathrm{dcol}_{k}(G)$ is unbounded for those graphs,
since, as remarked earlier, $\mathrm{dcol}_{k}(G)\geq\mathrm{wcol}_{\lfloor
k/2\rfloor+1}(G)$ for any graph $G$.

The one, trivial, example for which we can answer these questions is for
graphs $G$ without $K_{3}$-minor. As noted at the end of the previous section,
those graphs are bipartite, and hence $\chi(G^{[\natural
p]})\leq\chi(G^{\natural p})\leq 2$ for every odd $p$.

As we mentioned in Section 1, the proof of Theorem 1.7 actually gives that for
a class of graphs $\mathcal{K}$ with bounded expansion we can find a constant
$N=N(\mathcal{K},p)$ such that $\chi(G^{[\natural 1]}\cup G^{[\natural
3]}\cup\cdots\cup G^{[\natural p]})\leq N$. There are constructions that show
that this constant must grow with $p$, even if $\mathcal{K}$ is the class of
outerplanar graphs. One such construction appears in [21]. A very simple one,
which we sketch in Figure 3, can be found in [23].

Figure 3: Outerplanar graphs $G$ for which $\omega(G^{odd})$, and hence
$\chi(G^{odd})$,
can be arbitrarily large.

For a graph $G$, a natural generalisation of $G^{[\natural 1]}\cup
G^{[\natural 3]}\cup\dots\cup G^{[\natural p]}$ is the graph $G^{odd}$, which
has the same vertex set as $G$, and $xy$ is an edge in $G^{odd}$ if and only
if $x$ and $y$ have odd distance. Both constructions in the previous paragraph
tell us that for outerplanar graphs $G$ the chromatic number of $G^{odd}$ can
be arbitrarily large because the clique number $\omega(G^{odd})$ can be
arbitrarily large. This motivates the following open problem of Thomassé,
which appears in [20] (see also [21]).

######  Problem 5.2 ([20, Problem 11.2]).

Is there a function $f$ such that for every planar graph $G$ we have
$\chi(G^{odd})\leq f(\omega(G^{odd}))$ ?

Another area that is ripe for further research is the chromatic number of
exact distance graphs with even distance, for specific classes of graphs.
Theorem 1.6 (b) gives a first result for even distances. There is very little
we know about the dependencies between $\chi(G^{[\natural p]})$ and
$\mathrm{wcol}_{p}(G)$ for even $p$.

It is well-known, and easy to prove (see, e.g., [16]), that for every graph
$G$ we have $\chi(G^{2})\leq(2\mathrm{col}(G)-3)\cdot\Delta(G)$, hence
certainly $\chi(G^{[\natural 2]})\leq(2\mathrm{col}(G)-3)\cdot\Delta(G)$. This
suggests that there might exist a function $\varphi$ such that
$\chi(G^{[\natural p]})\leq\varphi(\mathrm{wcol}_{p-1}(G))\cdot\Delta(G)$, or
even $\chi(G^{[\natural
p]})\leq\varphi(\mathrm{wcol}_{p/2}(G))\cdot\Delta(G)$. We have not been able
to prove such a result. Neither do we know what the best value of $r(p)$
should be such that a result of the form $\chi(G^{[\natural
p]})\leq\varphi(\mathrm{wcol}_{r(p)}(G))\cdot\Delta(G)$ is possible for even
$p$.

## References

  * [1] G. Agnarsson, M.M. Halldórsson, _Coloring powers of planar graphs_. SIAM J. Discrete Math. 16 (2004), 651–662.
  * [2] O. Amini, L. Esperet, J. van den Heuvel, _A unified approach to distance-two colouring of graphs on surfaces_. Combinatorica 33 (2013), 253–296.
  * [3] M.O. Albertson, G.G. Chappell, H.A. Kierstead, A. Kündgen, and R. Ramamurthi, _Coloring with no 2-colored $P_{4}$’s_. Electron. J. Combin. 11 (2004).
  * [4] G. Chen and R.H. Schelp, _Graphs with linearly bounded Ramsey numbers_. J. Combin. Theory Ser. B 57 (1993), 138–149.
  * [5] M. Grohe, S. Kreutzer, R. Rabinovich, S. Siebertz, and K. Stavropoulos, _Colouring and covering nowhere dense graphs_. arXiv:1602.05926 [math.CO], 2016.
  * [6] G. Hajós, _Über eine Konstruktion nicht $n$-färbbarer Graphen_. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 116–117.
  * [7] J. van den Heuvel, P. Ossona de Mendez, D. Quiroz, R. Rabinovich, and S. Siebertz, _On the generalized colouring numbers of graphs that exclude a fixed minor_. arXiv:1602.09052 [math.CO], 2016.
  * [8] H.A. Kierstead, _A simple competitive graph coloring algorithm_. J. Combin. Theory Ser. B 78 (2000), 57–68.
  * [9] H.A. Kierstead and A.V. Kostochka, _Efficient graph packing via game colouring_. Combin. Probab. Comput. 18 (2009), 765–774.
  * [10] H.A. Kierstead and W.T. Trotter, _Planar graph coloring with an uncooperative partner_. J. Graph Theory 18 (1994), 569–584.
  * [11] H.A. Kierstead and W.T. Trotter, _Competitive colorings of oriented graphs_. Electron. J. Combin. 8 (2001).
  * [12] H.A. Kierstead and D. Yang, _Orderings on graphs and game coloring number_. Order 20 (2003), 255–264.
  * [13] F. Kramer and H. Kramer, _Un probleme de coloration des sommets d’un graphe_. C.R. Acad. Sci. Paris A 268 (1969), 46–48.
  * [14] F. Kramer and H. Kramer, _Ein Färbungsproblem der Knotenpunkte eines Graphen bezüglich der Distanz $p$_. Rev. Roumaine Math. Pures Appl. 14 (1969), 1031–1038.
  * [15] F. Kramer and H. Kramer, _A survey on the distance-colouring of graphs_. Discrete Math. 308 (2008), 422–426.
  * [16] S.O. Krumke, M.V. Marathe, and S.S. Ravi, _Approximation algorithms for channel assignment in radio networks_. In: _Dial M for Mobility; 2nd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications_. Dallas, Texas, 1998\.
  * [17] B. Mohar and C. Thomassen, _Graphs on Surfaces_. John Hopkins University Press, Baltimore, 2001.
  * [18] J. Nešetřil and P. Ossona de Mendez, _Tree-depth, subgraph coloring and homomorphism bounds_. European J. Combin. 27 (2006), 1022–1041.
  * [19] J. Nešetřil and P. Ossona de Mendez, _Grad and classes with bounded expansion. I. Decompositions_. European J. Combin. 29 (2008), 760–776.
  * [20] J. Nešetřil and P. Ossona de Mendez, _Sparsity – Graphs, Structures, and Algorithms_. Springer-Verlag, Berlin, Heidelberg, 2012.
  * [21] J. Nešetřil and P. Ossona de Mendez, _On low tree-depth decompositions_. Graphs Combin. 31 (2015), 1941–1963.
  * [22] A. Quilliot, _A short note about pursuit games played on a graph with a given genus_. J. Combin. Theory Ser. B 38 (1985) 89–92.
  * [23] D.A. Quiroz, _Colouring exact distance graphs of chordal graphs_. In preparation, 2016.
  * [24] G. Wegner, _Graphs with given diameter and a colouring problem_ , Technical Report, University of Dortmund, 1977.
  * [25] X. Zhu, _Refined activation strategy for the marking game_. J. Combin. Theory Ser. B 98 (2008), 1–18.
  * [26] X. Zhu, _Colouring graphs with bounded generalized colouring number_. Discrete Math. 309 (2009), 5562–5568.