Fine structure of 4-critical triangle-free graphs III. General surfaces
Zdenĕk Dvořák, Bernard Lidický · Iowa State University Digital Repository (Iowa State University) · 2018
Dvořák, Král', and Thomas [Three-Coloring Triangle-Free Graphs on Surfaces IV. Bounding Face Sizes of 4-Critical Graphs, preprint, arXiv:1404.6356v3, 2015; Three-Coloring Triangle-Free Graphs on Surfaces VI. 3-Colorability of Quadrangulations, preprint, arXiv:1509.01013, 2015] gave a description of the structure of triangle-free graphs on surfaces with respect to 3-coloring. Their description, however, contains two substructures (both related to graphs embedded in a plane with two precolored cycles) whose coloring properties are not entirely determined. In this paper, we fill these gaps.