List Coloring in the Absence of Two Subgraphs

Golovach, P. A.; Paulusma, D.

doi:10.1007/978-3-642-38233-8_24

List Coloring in the Absence of Two Subgraphs

Golovach, P. A.; Paulusma, D.

Authors

P. A. Golovach

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Contributors

Paul G. Spirakis
Editor

Maria Serna
Editor

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). List Coloring in the Absence of Two Subgraphs. In P. G. Spirakis, & M. Serna (Eds.), Algorithms and complexity : 8th International Conference, CIAC 2013, 22-24 May 2013, Barcelona, Spain ; proceedings (288-299). https://doi.org/10.1007/978-3-642-38233-8_24

Conference Name	8th International Conference, CIAC 2013
Conference Location	Barcelona, Spain
Publication Date	Jan 1, 2013
Deposit Date	Dec 20, 2014
Publicly Available Date	Jan 14, 2015
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