Article
4-Critical Graphs on Surfaces Without Contractible (≤4)-Cycles
SIAM Journal on Discrete Mathematics
(2014)
Abstract
We show that if G is a 4-critical graph embedded in a fixed surface Σ so that every
contractible cycle has length at least 5, then G can be expressed as G = G∪G1∪G2 ∪· · ·∪Gk, where
|V (G)| and k are bounded by a constant (depending linearly on the genus of Σ) and G1, . . . ,Gk 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.
Keywords
- graph coloring,
- contractible cycles,
- graphs of surfaces
Disciplines
Publication Date
2014
DOI
10.1137/130920952
Publisher Statement
Copyright 2014 Society for Industrial and Applied Mathematics
Citation Information
Zdeněk Dvořák and Bernard Lidicky. "4-Critical Graphs on Surfaces Without Contractible (≤4)-Cycles" SIAM Journal on Discrete Mathematics Vol. 28 Iss. 1 (2014) p. 521 - 552 Available at: http://works.bepress.com/bernard-lidicky/9/
Creative Commons license
This work is licensed under a Creative Commons CC_BY-NC International License.