4-critical graphs on surfaces without contractible (<=4)-cycles

Abstract

We show that if G is a 4-critical graph embedded in a fixed surface $\Sigma$ so that every contractible cycle has length at least 5, then G can be expressed as $G=G^{\prime }\cup G_1\cup G_2\cup ...\cup G_k$, where $|V(G^{\prime })|$ and $k$ are bounded by a constant (depending linearly on the genus of $\Sigma$) and $G_1\dots ,G_k$ are graphs (of unbounded size) whose structure we describe exactly. The proof is computer-assisted - we use computer to enumerate all plane 4-critical graphs of girth 5 with a precolored cycle of length at most 16, that are used in the basic case of the inductive proof of the statement.

52 pages, 19 figures

References in corpus (1)

• Short proofs of coloring theorems on planar graphs

Cited by in corpus (4)

• 3-coloring triangle-free planar graphs with a precolored 8-cycle
• Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles
• 3-coloring triangle-free planar graphs with a precolored 9-cycle
• Fine structure of 4-critical triangle-free graphs I. Planar graphs with two triangles and 3-colorability of chains