Skip to main content

Research Repository

Advanced Search

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





You might also like



Downloadable Citations