List Coloring in the Absence of Two Subgraphs

Golovach, P. A.; Paulusma, D.

Abstract

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 2 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 ! f1; 2; : : :g such that (i) c(u) 6= c(v) whenever uv 2 E and (ii) c(u) 2 L(u) for all u 2 V . If a graph G has no induced subgraph isomorphic to some graph of a pair fH1;H2g, then G is called (H1;H2)-free. We completely characterize the complexity of List Coloring for (H1;H2)-free graphs.

Citation

Golovach, P. A., & Paulusma, D. (2013, December). List Coloring in the Absence of Two Subgraphs. Presented at 8th International Conference, CIAC 2013, Barcelona, Spain

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 8th International Conference, CIAC 2013
• Publication Date: Jan 1, 2013
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 14, 2015
• Print ISSN: 0302-9743
• Volume: 7878
• Pages: 288-299
• Series Title: Lecture notes in computer science
• Series Number: 7878
• Series ISSN: 0302-9743,1611-3349
• Book Title: Algorithms and complexity : 8th International Conference, CIAC 2013, 22-24 May 2013, Barcelona, Spain ; proceedings.
• ISBN: 9783642382321
• DOI: https://doi.org/10.1007/978-3-642-38233-8_24
• Public URL: https://durham-repository.worktribe.com/output/1153948