On Distance Coloring
| dc.contributor.author | Kozen, Dexter | en_US |
| dc.contributor.author | Sharp, Alexa | en_US |
| dc.date.accessioned | 2007-07-05T18:21:41Z | |
| dc.date.available | 2007-07-05T18:21:41Z | |
| dc.date.issued | 2007-06-29 | en_US |
| dc.description.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. | en_US |
| dc.format.extent | 245082 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2007-2084 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/7878 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer information science | en_US |
| dc.subject | Computational Complexity | en_US |
| dc.subject | technical report | en_US |
| dc.title | On Distance Coloring | en_US |
| dc.type | technical report | en_US |
Files
Original bundle
1 - 1 of 1