4-Critical Graphs on Surfaces Without Contractible $(\le\!4)$-Cycles
Zdenĕk Dvořák, Bernard Lidický · SIAM Journal on Discrete Mathematics · 2014
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'\cup G_1\cup G_2\cup\cdots\cup G_k$, where $|V(G')|$ and $k$ are bounded by a constant (depending linearly on the genus of $\Sigma$) and $G_1, \ldots, G_k$ are graphs (of unbounded size) whose structure we describe exactly. The proof is computer assisted---we use a 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.