Skip to main content


eCommons@Cornell >
Faculty of Computing and Information Science >
Computing and Information Science >
Computing and Information Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: On Distance Coloring
Authors: Kozen, Dexter
Sharp, Alexa
Keywords: computer information science
Computational Complexity
technical report
Issue Date: 29-Jun-2007
Publisher: Cornell University
Abstract: Call 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.
Appears in Collections:Computing and Information Science Technical Reports

Files in This Item:

File Description SizeFormat
TR2007-2084.pdf239.34 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us