3-list-coloring graphs of girth at least five on surfaces

DOI10.1016/J.JCTB.2020.09.013MaRDI QIDQ2222041zbMATH OpenOpenAlexFDO

Authors Luke Postle

Publication date 3 February 2021

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

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

zbMATH Keywords

graphs on surfaceslist coloringstrongly hyperbolic families

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Grotzsch proved that every triangle-free planar graph is 3-colorable. Thomassen proved that every planar graph of girth at least five is 3-choosable. As for other surfaces, Thomassen proved that there are only finitely many 4-critical graphs of girth at least five embeddable in any fixed surface. This implies a linear-time algorithm for deciding 3-colorablity for graphs of girth at least five on any fixed surface. Dvorak, Kral and Thomas strengthened Thomassen's result by proving that the number of vertices in a 4-critical graph of girth at least five is linear in its genus. They used this result to prove Havel's conjecture that a planar graph whose triangles are pairwise far enough apart is 3-colorable. As for list-coloring, Dvorak proved that a planar graph whose cycles of size at most four are pairwise far enough part is 3-choosable. In this article, we generalize these results. First we prove a linear isoperimetric bound for 3-list-coloring graphs of girth at least five. Many new results then follow from the theory of hyperbolic families of graphs developed by Postle and Thomas. In particular, it follows that there are only finitely many 4-list-critical graphs of girth at least five on any fixed surface, and that in fact the number of vertices of a 4-list-critical graph is linear in its genus. This provides independent proofs of the above results while generalizing Dvorak's result to graphs on surfaces that have large edge-width and yields a similar result showing that a graph of girth at least five with crossings pairwise far apart is 3-choosable. Finally, we generalize to surfaces Thomassen's result that every planar graph of girth at least five has exponentially many distinct 3-list-colorings. Specifically, we show that every graph of girth at least five that has a 3-list-coloring has $2^{Omega(n)-O(g)}$ distinct 3-list-colorings.

Recommendations

• 3-list-coloring planar graphs of girth 5
• The chromatic number of a graph of girth 5 on a fixed surface
• List-color-critical graphs on a fixed surface
• A short list color proof of Grötzsch's theorem
• \((3a:a)\)-list-colorability of embedded graphs of girth at least five

Cites work

• \((3a:a)\)-list-colorability of embedded graphs of girth at least five
• 3-choosability of planar graphs with \((\leqslant 4)\)-cycles far apart
• 3-list-coloring planar graphs of girth 5
• A not 3-choosable planar graph without 3-cycles
• A short list color proof of Grötzsch's theorem
• Coloring triangle-free graphs on surfaces
• Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.
• Graphs on surfaces
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• Hyperbolic families and coloring graphs on surfaces
• List-coloring embedded graphs
• Many 3-colorings of triangle-free planar graphs
• On a conjecture of B. Grünbaum
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The chromatic number of a graph of girth 5 on a fixed surface
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies

Cited in

(13)

• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
• 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.
• Colouring graphs on surfaces
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• From the plane to higher surfaces
• Hyperbolic families and coloring graphs on surfaces
• Exponentially many 4-list-colorings of triangle-free graphs on surfaces
• List-color-critical graphs on a fixed surface
• \((3a:a)\)-list-colorability of embedded graphs of girth at least five
• Hyperbolicity theorems for correspondence colouring
• On decidability of hyperbolicity
• Coloring face hypergraphs on surfaces

This page was built for publication: 3-list-coloring graphs of girth at least five on surfaces

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