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 many4-critical graphs of girth at least five embeddable in any fixed surface. Thisimplies a linear-time algorithm for deciding 3-colorablity for graphs of girthat least five on any fixed surface. Dvorak, Kral and Thomas strengthenedThomassen's result by proving that the number of vertices in a 4-critical graphof girth at least five is linear in its genus. They used this result to proveHavel's conjecture that a planar graph whose triangles are pairwise far enoughapart is 3-colorable. As for list-coloring, Dvorak proved that a planar graphwhose 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 linearisoperimetric bound for 3-list-coloring graphs of girth at least five. Many newresults then follow from the theory of hyperbolic families of graphs developedby Postle and Thomas. In particular, it follows that there are only finitelymany 4-list-critical graphs of girth at least five on any fixed surface, andthat in fact the number of vertices of a 4-list-critical graph is linear in itsgenus. This provides independent proofs of the above results while generalizingDvorak's result to graphs on surfaces that have large edge-width and yields asimilar result showing that a graph of girth at least five with crossingspairwise far apart is 3-choosable. Finally, we generalize to surfacesThomassen's result that every planar graph of girth at least five hasexponentially many distinct 3-list-colorings. Specifically, we show that everygraph of girth at least five that has a 3-list-coloring has$2^{Omega(n)-O(g)}$ distinct 3-list-colorings.
展开▼
