5-list-coloring planar graphs with distant precolored vertices
From MaRDI portal
Publication:345086
DOI10.1016/J.JCTB.2016.06.006zbMATH Open1350.05019arXiv1209.0366OpenAlexW3105851171MaRDI QIDQ345086FDOQ345086
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)
Abstract: We answer positively the question of Albertson asking whether every planar graph can be -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.
Full work available at URL: https://arxiv.org/abs/1209.0366
Recommendations
Cites Work
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Title not available (Why is that?)
- Every planar graph is 5-choosable
- Color-critical graphs on a fixed surface
- Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.
- Title not available (Why is that?)
- Exponentially many 5-list-colorings of planar graphs
- The non-existence of colorings
- List colourings of planar graphs
- You can't paint yourself into a corner
- Dirac's map-color theorem for choosability
- 5-choosability of graphs with crossings far apart
- List precoloring extension in planar graphs
Cited In (12)
- 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
- Hyperbolic families and coloring graphs on surfaces
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)
