Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

DOI10.1007/978-3-319-29516-9_9zbMath1474.68216arXiv1506.06564OpenAlexW2963258127MaRDI QIDQ2798222

Matthew Johnson, Konrad K. Dabrowski, François Dross, Daniël Paulusma

Publication date: 4 April 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.06564

zbMATH Keywords

planar graphschoosabilitymaximum degreelist colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

List-coloring -- parameterizing from triviality ⋮ A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs ⋮ Colouring H-free graphs of bounded diameter. ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ A complexity dichotomy for critical values of the b-chromatic number of graphs

This page was built for publication: Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs