Title:
Distance Coloring
Authors:
Sharp, Alexa
Abstract:
Given a graph G = (V,E), a (d,k)-coloring is a function from the vertices V to colors {1, 2, ...,k} such that any two vertices within distance d of each other are assigned different colors. We determine the complexity of the (d,k)-coloring problem for all d and k, and enumerate some interesting properties of (d,k)-colorable graphs. Our main result is the discovery of a dichotomy between polynomial and NP-hard instances: for fixed d ≥ 2, the distance coloring problem is polynomial time for TeX and NP-hard for TeX .
Citation:
Sharp, A. 2007. "Distance Coloring," in Proceedings of the 15th Annual European Symposium on Algorithms, 2007. Lecture Notes In Computer Science.
Publisher:
Springer
DATE ISSUED:
2007
Department:
Computer Science
Type:
Conference Proceedings
PUBLISHED VERSION:
10.1007/978-3-540-75520-3_46
PERMANENT LINK:
http://hdl.handle.net/11282/310322

Full metadata record

DC FieldValue Language
dc.contributor.authorSharp, Alexaen_US
dc.date.accessioned2013-12-23T16:30:29Z-
dc.date.available2013-12-23T16:30:29Z-
dc.date.issued2007en
dc.identifier.citationSharp, A. 2007. "Distance Coloring," in Proceedings of the 15th Annual European Symposium on Algorithms, 2007. Lecture Notes In Computer Science.en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/11282/310322-
dc.description.abstractGiven a graph G = (V,E), a (d,k)-coloring is a function from the vertices V to colors {1, 2, ...,k} such that any two vertices within distance d of each other are assigned different colors. We determine the complexity of the (d,k)-coloring problem for all d and k, and enumerate some interesting properties of (d,k)-colorable graphs. Our main result is the discovery of a dichotomy between polynomial and NP-hard instances: for fixed d ≥ 2, the distance coloring problem is polynomial time for TeX and NP-hard for TeX .en_US
dc.publisherSpringeren_US
dc.identifier.doi10.1007/978-3-540-75520-3_46-
dc.subject.departmentComputer Scienceen_US
dc.titleDistance Coloringen_US
dc.typeConference Proceedingsen_US
dc.identifier.journalLecture Notes In Computer Scienceen_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.