Fine structure of 4-critical triangle-free graphs III. General surfacesSIAM Journal on Discrete Mathematics
Publication VersionPublished Version
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 OwnerSociety for Industrial and Applied Mathematics
Citation InformationZdenek 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.