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

DOI10.1016/J.JCTB.2015.12.005MaRDI QIDQ273167zbMATH OpenOpenAlexFDO

Authors Luke Postle, Robin Thomas

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)

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.

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

Cites work

• 5-list-coloring planar graphs with distant precolored vertices
• Color-critical graphs on a fixed surface
• Every planar graph is 5-choosable
• 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

Cited in

(7)

• Hyperbolic families and coloring graphs on surfaces
• \((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

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)