Kozen, DexterSharp, Alexa2007-07-052007-07-052007-06-29http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2007-2084https://hdl.handle.net/1813/7878Call a connected undirected graph (d,c)-colorable if there is a vertex coloring using at most c colors such that no two vertices of distance d or less have the same color. It is well known that (1,2)-colorability is decidable in linear time, but (1,c)-colorability for c greater than or equal to 3 is NP-complete. Sharp (2007) shows that for fixed d greater than or equal to 2, the (d,c)-colorability problem is solvable in linear time for c less than or equal to 3d/2 and NP-complete otherwise. In this note we give an alternative construction that improves the upper time bound as a function of d for the case c less than or equal to 3d/2. The construction entails a generalization of the notion of tree decomposition and bounded treewidth (Robertson and Seymour 1986) to arbitrary overlay graphs, not just trees, which may be of independent interest.245082 bytesapplication/pdfen-UScomputer information scienceComputational Complexitytechnical reporttechnical report