On Distance Coloring

An undirected graph

G

 = (

V

,

E

) is (

d

,

k

)

-colorable

if there is a vertex coloring using at most

k

colors such that no two vertices within distance

d

have the same color. It is well known that (1,2)-colorability is decidable in linear time, and that (1,

k

)-colorability is

NP

-complete for

k

 ≥ 3. This paper presents the complexity of (

d

,

k

)-coloring for general

d

and

k

, and enumerates some interesting properties of (

d

,

k

)-colorable graphs. The main result is the dichotomy between polynomial and

NP

-hard instances: for fixed

d

 ≥ 2, the distance coloring problem is polynomial time for

$k \leq \lfloor \frac{3d}{2} \rfloor$

and NP-hard for

$k > \lfloor \frac{3d}{2} \rfloor$

. We present a reduction in the latter case, as well as an algorithm in the former. The algorithm entails several innovations that may be of independent interest: a generalization of tree decompositions to overlay graphs other than trees; a general construction that obtains such decompositions from certain classes of edge partitions; and the use of homology to analyze the cycle structure of colorable graphs. This paper is both a combining and reworking of the papers of Sharp and Kozen [14, 10].