Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two

DOI10.1016/J.JCTB.2017.06.004zbMATH Open1375.05105OpenAlexW2963803488MaRDI QIDQ1682205FDOQ1682205

Authors Luke Postle, Robin Thomas 

Publication date 28 November 2017

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

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

zbMATH Keywords

planar graphlist-coloring

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 non-empty sets. By an $L$-coloring of $G$ we mean a (proper) coloring $phi$ of $G$ such that $phi(v)inL(v)$ for every vertex $v$ of $G$. Thomassen proved that if $v_1,v_{2}inV(C)$ are adjacent, $L(v_1)eL(v_2)$, $|L(v)|ge3$ for every $vinV(C)-v_1,v_2$ and $|L(v)|ge5$ for every $vinV(G)-V(C)$, then $G$ has an $L$-coloring. What happens when $v_1$ and $v_2$ are not adjacent? Then an $L$-coloring need not exist, but in the first paper of this series we have shown that it exists if $|L(v_1)|,|L(v_2)|ge2$. Here we characterize when an $L$-coloring exists if $|L(v_1)|ge1$ and $|L(v_2)|ge2$. This result is a lemma toward a more general theorem along the same lines, which we will use to prove that minimally non-$L$-colorable planar graphs with two precolored cycles of bounded length are of bounded size. The latter result has a number of applications which we pursue elsewhere.

Recommendations

• Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs
• Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.
• Exponentially many 5-list-colorings of planar graphs
• 5-list-coloring planar graphs with distant precolored vertices
• On list-coloring outerplanar graphs

Cites work

• 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. I. Two lists of size two in planar graphs
• List colourings of planar graphs
• On list-coloring extendable outerplanar graphs

Cited in

(6)

• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.
• Exponentially many 5-list-colorings of planar graphs
• Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs
• The polynomial method for list-colouring extendability of outerplanar graphs
• Hyperbolic families and coloring graphs on surfaces

This page was built for publication: Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two

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