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.
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015) |
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 | Aug 5, 2017 |
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
(326 Kb)
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
Classifying Subset Feedback Vertex Set for H-free graphs
(2022)
Presentation / Conference Contribution
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
An algorithmic framework for locally constrained homomorphisms
(2022)
Presentation / Conference Contribution
The Complexity of L(p,q)-Edge-Labelling
(2022)
Presentation / Conference Contribution
Computing Balanced Solutions for Large International Kidney Exchange Schemes
(2022)
Presentation / Conference Contribution
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