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

DOI10.1016/J.JCTB.2015.12.005zbMATH Open1334.05043arXiv1505.05927OpenAlexW1613467653MaRDI QIDQ273167FDOQ273167

Authors: Luke Postle, Robin Thomas 

Publication date: 21 April 2016

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

Abstract: Let $G$ be a plane graph with outer cycle $C$ and let $(L(v):vinV(G))$ be a family of sets such that $|L(v)|ge5$ for every $vinV(G)$. By an $L$-coloring of a subgraph $J$ of $G$ we mean a (proper) coloring $phi$ of $J$ such that $phi(v)inL(v)$ for every vertex $v$ of $J$. We prove a conjecture of Dvorak et al. that if $H$ is a minimal subgraph of $G$ such that $C$ is a subgraph of $H$ and every $L$-coloring of $C$ that extends to an $L$-coloring of $H$ also extends to an $L$-coloring of $G$, then $|V(H)|le19|V(C)|$. This is a lemma that plays an important role in subsequent papers, because it motivates the study of graphs embedded in surfaces that satisfy an isoperimetric inequality suggested by this result. Such study turned out to be quite profitable for the subject of list coloring graphs on surfaces.

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

Recommendations

• Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs
• Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two
• A Five-Color Theorem for Graphs on Surfaces
• 3-list-coloring graphs of girth at least five on surfaces
• List-color-critical graphs on a fixed surface
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• Color-critical graphs on a fixed surface
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• Exponentially many 5-list-colorings of planar graphs
• List-coloring graphs on surfaces with varying list-sizes

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)

Cites Work

• 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
• 5-list-coloring planar graphs with distant precolored vertices

Cited In (7)

• \((3a:a)\)-list-colorability of embedded graphs of girth at least five
• 5-list-coloring planar graphs with distant precolored vertices
• Distributed coloring in sparse graphs with fewer colors
• Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two
• 3-list-coloring graphs of girth at least five on surfaces
• Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs
• Hyperbolic families and coloring graphs on surfaces

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

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