Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
From MaRDI portal
Publication:2200929
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.
Recommendations
- 3-list-coloring graphs of girth at least five 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
- Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
- Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
- Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
- (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
- scientific article; zbMATH DE number 7145382
- Coloring triangle-free graphs on surfaces
- Coloring Triangle-Free Graphs on Surfaces
Cites work
- 3-list-coloring planar graphs of girth 5
- 4-chromatic projective graphs
- 4-critical graphs on surfaces without contractible ( 4)-cycles
- A short list color proof of Grötzsch's theorem
- Coloring graphs with fixed genus and girth
- Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\)
- Graph theory with applications
- Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
- scientific article; zbMATH DE number 3482373 (Why is no real title available?)
- On a conjecture of B. Grünbaum
- The chromatic number of a graph of girth 5 on a fixed surface
- Three-coloring Klein bottle graphs of girth five
- Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
- Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
- Three-coloring triangle-free planar graphs in linear time
Cited in
(17)- Three-coloring graphs embedded on surfaces with all faces even-sided
- Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
- 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
- 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
- Hyperbolic families and coloring graphs on surfaces
- Fine structure of 4-critical triangle-free graphs. III: General surfaces
- 4-critical graphs on surfaces without contractible ( 4)-cycles
- \((3a:a)\)-list-colorability of embedded graphs of girth at least five
- scientific article; zbMATH DE number 7145382 (Why is no real title available?)
- Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
- Precoloring extension in planar near-Eulerian-triangulations
- On decidability of hyperbolicity
- Precoloring extension in planar near-Eulerian-triangulations
- Precoloring extension in planar near-Eulerian-triangulations (extended abstract)
- Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
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)
