Skip to main content

Research Repository

Advanced Search

Closing complexity gaps for coloring problems on H-free graphs

Golovach, P. A.; Paulusma, D.; Song, J.

Authors

P. A. Golovach

J. Song



Contributors

Kun-Mao Chao
Editor

Tsan-sheng Hsu
Editor

Der-Tsai Lee
Editor

Abstract

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then c is a k-coloring. The Coloring problem is to test whether a graph has a coloring with at most k colors for some integer k. The Precoloring Extension problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The List Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u). By imposing an upper bound ℓ on the size of each L(u) we obtain the ℓ-List Coloring problem. We first classify the Precoloring Extension problem and the ℓ-List Coloring problem for H-free graphs. We then show that 3-List Coloring is NP-complete for n-vertex graphs of minimum degree n − 2, i.e., for complete graphs minus a matching, whereas List Coloring is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n − 2. Finally, for a fixed integer k > 0, the List k-Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u) that must be a subset of {1,…,k}. We show that List 4-Coloring is NP-complete for P6-free graphs, where P6 is the path on six vertices. This completes the classification of List k-Coloring for P6-free graphs.

Citation

Golovach, P. A., Paulusma, D., & Song, J. (2012). Closing complexity gaps for coloring problems on H-free graphs. In K. Chao, T. Hsu, & D. Lee (Eds.), Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings (14-23). https://doi.org/10.1007/978-3-642-35261-4_5

Publication Date 2012
Deposit Date Mar 11, 2013
Volume 7676
Pages 14-23
Series Title Lecture notes in computer science
Series Number 7676
Series ISSN 0302-9743,1611-3349
Book Title Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings.
ISBN 9783642352607
DOI https://doi.org/10.1007/978-3-642-35261-4_5
Keywords Graph coloring, Precoloring extension, List coloring, Forbidden.
Public URL https://durham-repository.worktribe.com/output/1157027
Additional Information Series: Lecture Notes in Computer Science, Volume 7676