Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Open problems on graph coloring for special graph classes
Paulusma, D.
Authors
Contributors
Ernst W. Mayr
Editor
Abstract
For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c:V→{1,2,…}c:V→{1,2,…} such that c(u)≠c(v)c(u)≠c(v) for every edge uv∈Euv∈E. We survey known results on the computational complexity of Coloring for graph classes that are hereditary or for which some graph parameter is bounded. We also consider coloring variants, such as precoloring extensions and list colorings and give some open problems in the area of on-line coloring.
Citation
Paulusma, D. (2016). Open problems on graph coloring for special graph classes. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (16-30). https://doi.org/10.1007/978-3-662-53174-7_2
Conference Name | 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015) |
---|---|
Conference Location | Munich, Germany |
Start Date | Jun 17, 2015 |
End Date | Jun 19, 2015 |
Acceptance Date | Aug 12, 2015 |
Online Publication Date | Aug 5, 2016 |
Publication Date | Aug 5, 2016 |
Deposit Date | Aug 12, 2015 |
Publicly Available Date | Mar 29, 2024 |
Pages | 16-30 |
Series Title | Lecture notes in computer science |
Series Number | 9224 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers. |
ISBN | 9783662531730 |
DOI | https://doi.org/10.1007/978-3-662-53174-7_2 |
Public URL | https://durham-repository.worktribe.com/output/1152179 |
Additional Information | Conference dates: 17-19 June 2015 |
Files
Accepted Conference Proceeding
(0)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-53174-7_2
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