Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.

DOI10.1016/j.jctb.2015.12.005zbMath1334.05043arXiv1505.05927OpenAlexW1613467653MaRDI QIDQ273167

Robin Thomas, Luke Postle

Publication date: 21 April 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

planar graph5-list-coloringcritical graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (6)

Hyperbolic families and coloring graphs on surfaces ⋮ 5-list-coloring planar graphs with distant precolored vertices ⋮ 3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle ⋮ $(3a:a)$-List-Colorability of Embedded Graphs of Girth at Least Five ⋮ 3-list-coloring graphs of girth at least five on surfaces ⋮ Distributed coloring in sparse graphs with fewer colors

Cites Work

• 5-list-coloring planar graphs with distant precolored vertices
• Every planar graph is 5-choosable
• Color-critical graphs on a fixed surface
• Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two
• Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs

This page was built for publication: Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.