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
- scientific article; zbMATH DE number 3482373 (Why is no real title available?)
- 3-list-coloring planar graphs of girth 5
- 4-chromatic projective graphs
- 4-critical graphs on surfaces without contractible \((\leq 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
- 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
(13)- (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
- Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
- \((3a:a)\)-list-colorability of embedded graphs of girth at least five
- scientific article; zbMATH DE number 7145382 (Why is no real title available?)
- Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
- Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
- Three-coloring graphs embedded on surfaces with all faces even-sided
- 3-list-coloring graphs of girth at least five on surfaces
- Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
- Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
- 4-critical graphs on surfaces without contractible \((\leq 4)\)-cycles
- Fine structure of 4-critical triangle-free graphs. III: General surfaces
- Hyperbolic families and coloring graphs on surfaces
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)
