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)- Hyperbolic families and coloring graphs on surfaces
- \((3a:a)\)-list-colorability of embedded graphs of girth at least five
- Three-coloring graphs embedded on surfaces with all faces even-sided
- 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
- Fine structure of 4-critical triangle-free graphs. III: General surfaces
- 3-list-coloring graphs of girth at least five on surfaces
- Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
- Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
- 4-critical graphs on surfaces without contractible \((\leq 4)\)-cycles
- (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
- scientific article; zbMATH DE number 7145382 (Why is no real title available?)
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)
