List coloring in the absence of two subgraphs

Golovach, P.A.; Paulusma, D.

Abstract

A list assignment of a graph G=(V,E) is a function L that assigns a list L(u) of so-called admissible colors to each u∈V. The List Coloring problem is that of testing whether a given graph G=(V,E) has a coloring c that respects a given list assignment L, i.e., whether G has a mapping c:V→{1,2,…} such that (i) c(u)≠c(v) whenever uv∈E and (ii) c(u)∈L(u) for all u∈V. If a graph G has no induced subgraph isomorphic to some graph of a pair {H1,H2}, then G is called (H1,H2)-free. We completely characterize the complexity of List Coloring for (H1,H2)-free graphs.

Citation

Golovach, P., & Paulusma, D. (2014). List coloring in the absence of two subgraphs. Discrete Applied Mathematics, 166, 123-130. https://doi.org/10.1016/j.dam.2013.10.010

• Journal Article Type: Article
• Publication Date: Mar 1, 2014
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 6, 2015
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 166
• Pages: 123-130
• DOI: https://doi.org/10.1016/j.dam.2013.10.010
• Keywords: List coloring, Forbidden induced subgraph, Computational complexity
• Public URL: https://durham-repository.worktribe.com/output/1415009