Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five

DOI10.1016/J.JCTB.2020.06.005zbMATH Open1448.05074arXiv1402.4710OpenAlexW3038385145MaRDI QIDQ2200929FDOQ2200929

Robin Thomas, Daniel Král', Zdeněk Dvořák

Publication date: 24 September 2020

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

Abstract: We show that the size of a 4-critical graph of girth at least five is bounded by a linear function of its genus. This strengthens the previous bound on the size of such graphs given by Thomassen. It also serves as the basic case for the description of the structure of 4-critical triangle-free graphs embedded in a fixed surface, presented in a future paper of this series.

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

zbMATH Keywords

surfacestriangle-freecoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• The chromatic number of a graph of girth 5 on a fixed surface
• A short list color proof of Grötzsch's theorem
• Three-coloring Klein bottle graphs of girth five
• 3-list-coloring planar graphs of girth 5
• Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
• Three-coloring triangle-free planar graphs in linear time
• Coloring graphs with fixed genus and girth
• 4-chromatic projective graphs
• On a conjecture of B. Grünbaum
• Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\)
• 4-Critical Graphs on Surfaces Without Contractible $(\le\!4)$-Cycles
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• Three-coloring graphs embedded on surfaces with all faces even-sided
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• 3-list-coloring graphs of girth at least five on surfaces
• Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
• $(3a:a)$-List-Colorability of Embedded Graphs of Girth at Least Five
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
• Title not available (Why is that?)
• Hyperbolic families and coloring graphs on surfaces

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• 3-list-coloring graphs of girth at least five on surfaces 👍 👎
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface 👍 👎
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk 👍 👎
• Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle. 👍 👎
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs 👍 👎
• Coloring Triangle-Free Graphs on Surfaces 👍 👎
• Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies 👍 👎
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm 👍 👎

This page was built for publication: Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five

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