Publication at Faculty of Mathematics and Physics |
2014
Abstract
We show that if G is a 4-critical graph embedded in a fixed surface S so that every contractible cycle has length at least 5, then G can be expressed as G = G'boolean OR G(1)boolean OR G(2)boolean OR ... boolean OR G(k), where vertical bar V (C')vertical bar| and k are bounded by a constant (depending linearly on the genus of Sigma) and C-1, ... , C-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.