P. A. Golovach
List Coloring in the Absence of Two Subgraphs
Golovach, P. A.; Paulusma, D.
Authors
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 |
Files
Accepted Conference Proceeding
(352 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-38233-8_24
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search