Article
Fine structure of 4-critical triangle-free graphs III. General surfaces
SIAM Journal on Discrete Mathematics
Document Type
Article
Disciplines
Publication Version
Published Version
Publication Date
1-1-2018
DOI
10.1137/15M1023403
Abstract
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.
Copyright Owner
Society for Industrial and Applied Mathematics
Copyright Date
2018
Language
en
File Format
application/pdf
Citation Information
Zdenek Dvorak and Bernard Lidicky. "Fine structure of 4-critical triangle-free graphs III. General surfaces" SIAM Journal on Discrete Mathematics Vol. 32 Iss. 1 (2018) p. 94 - 105 Available at: http://works.bepress.com/bernard-lidicky/46/
This article is published as Dvorák, Zdenek, and Bernard Lidický. "Fine structure of 4-critical triangle-free graphs III. General surfaces." SIAM Journal on Discrete Mathematics 32, no. 1 (2018): 94-105. doi: 10.1137/15M1023403. Posted with permission.