Hard coloring problems in low degree planar bipartite graphs

DOI10.1016/j.dam.2006.03.014zbMath1099.05032OpenAlexW2062644202MaRDI QIDQ2506359

Miroslav Chlebík, Janka Chlebíková

Publication date: 28 September 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://researchportal.port.ac.uk/portal/en/publications/hard-coloring-problems-in-low-degree-planar-bipartite-graphs(ffc3c6c0-fce4-432d-9aa8-fe75f280aa65).html

zbMATH Keywords

planar graphslist coloringprecoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (10)

Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ On two coloring problems in mixed graphs ⋮ Coloring graphs characterized by a forbidden subgraph ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Complexity of two coloring problems in cubic planar bipartite mixed graphs ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Precoloring extension. I: Interval graphs
• Algorithmic complexity of list colorings
• Scheduling with incompatible jobs
• The colour theorems of Brooks and Gallai extended
• Generalized coloring for tree-like graphs
• Graph colorings with local constraints -- a survey
• Approximation results for the optimum cost chromatic partition problem
• Precoloring Extensions of Brooks' Theorem
• A Brooks-Type Theorem for the Generalized List T-Coloring
• Hard tiling problems with simple tiles

This page was built for publication: Hard coloring problems in low degree planar bipartite graphs