Closing complexity gaps for coloring problems on H-free graphs

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

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 Listk -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 Listk -Coloring for P6-free graphs.

Citation

Golovach, P., Paulusma, D., & Song, J. (2014). Closing complexity gaps for coloring problems on H-free graphs. Information and Computation, 237, 204-214. https://doi.org/10.1016/j.ic.2014.02.004

• Journal Article Type: Article
• Publication Date: Oct 1, 2014
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 8, 2015
• Journal: Information and Computation
• Print ISSN: 0890-5401
• Electronic ISSN: 1090-2651
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 237
• Pages: 204-214
• DOI: https://doi.org/10.1016/j.ic.2014.02.004
• Keywords: Graph coloring, Precoloring extension, List coloring, Forbidden induced subgraph.
• Public URL: https://durham-repository.worktribe.com/output/1439415