Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs
Preprint
Abstract
Let G be a 4-critical graph with t triangles, embedded in a surface of genus g. Let c be the number of 4-cycles in G that do not bound a 2-cell face. We prove that the sum of lengths of (>=5)-faces of G is at most linear in g+t+c-1.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Three-coloring triangle-free planar graphs in linear timeACM Transactions on Algorithms, 2011
- Three-coloring Klein bottle graphs of girth fiveJournal of Combinatorial Theory, Series B, 2004
- The chromatic number of a graph of girth 5 on a fixed surfaceJournal of Combinatorial Theory, Series B, 2003
- Coloring graphs with fixed genus and girthTransactions of the American Mathematical Society, 1997
- Three-Coloring Graphs Embedded on Surfaces with All Faces Even-SidedJournal of Combinatorial Theory, Series B, 1995
- 3-List-Coloring Planar Graphs of Girth 5Journal of Combinatorial Theory, Series B, 1995
- Graph minors. VII. Disjoint paths on a surfaceJournal of Combinatorial Theory, Series B, 1988