Open problems on graph coloring for special graph classes

Paulusma, D.

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. (2015, June). Open problems on graph coloring for special graph classes. Presented at 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany

• 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
• Print ISSN: 0302-9743
• 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