5-list-coloring planar graphs with distant precolored vertices

DOI10.1016/J.JCTB.2016.06.006MaRDI QIDQ345086zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Bernard Lidický, Bojan Mohar, Luke Postle

Publication date 25 November 2016

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

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

zbMATH Keywords

list coloringplanar graphsprecoloring extension

Mathematics Subject Classification ID

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

Abstract: We answer positively the question of Albertson asking whether every planar graph can be $5$-list-colored even if it contains precolored vertices, as long as they are sufficiently far apart from each other. In order to prove this claim, we also give bounds on the sizes of graphs critical with respect to 5-list coloring. In particular, if G is a planar graph, H is a connected subgraph of G and L is an assignment of lists of colors to the vertices of G such that |L(v)| >= 5 for every v in V(G)-V(H) and G is not L-colorable, then G contains a subgraph with O(|H|^2) vertices that is not L-colorable.

Recommendations

• List precoloring extension in planar graphs
• A note on planar 5-list colouring: Non-extendability at distance 4
• 3-list-coloring planar graphs of girth 5
• Exponentially many 5-list-colorings of planar graphs
• List-coloring graphs on surfaces with varying list-sizes

Cites work

• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 7051286 (Why is no real title available?)
• 5-choosability of graphs with crossings far apart
• Color-critical graphs on a fixed surface
• Dirac's map-color theorem for choosability
• Every planar graph is 5-choosable
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Exponentially many 5-list-colorings of planar graphs
• Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.
• List colourings of planar graphs
• List precoloring extension in planar graphs
• The non-existence of colorings
• You can't paint yourself into a corner

Cited in

(12)

• Hyperbolic families and coloring graphs on surfaces
• Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.
• Colorings, transversals, and local sparsity
• Exponentially many 5-list-colorings of planar graphs
• A note on planar 5-list colouring: Non-extendability at distance 4
• List colorings of \(K_5\)-minor-free graphs with special list assignments
• Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two
• List-coloring graphs on surfaces with varying list-sizes
• 5-choosability of graphs with crossings far apart
• List precoloring extension in planar graphs
• On Baire measurable colorings of group actions
• Flexibility of triangle‐free planar graphs

This page was built for publication: 5-list-coloring planar graphs with distant precolored vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345086)