Article
Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains
SIAM Journal on Discrete Mathematics
Document Type
Article
Publication Version
Published Version
Publication Date
1-1-2018
DOI
10.1137/15M1023385
Abstract
Aksenov proved that in a planar graph $G$ with at most one triangle, every precoloring of a 4-cycle can be extended to a 3-coloring of $G$. We give an exact characterization of planar graphs with two triangles in which some precoloring of a 4-cycle does not extend. We apply this characterization to solve the precoloring extension problem from two 4-cycles in a triangle-free planar graph in the case that the precolored 4-cycles are separated by many disjoint 4-cycles. The latter result is used in follow-up papers [SIAM J. Discrete Math., 31 (2017), pp. 865--874; SIAM J. Discrete Math., 32 (2018), pp. 94--105] to give detailed information about the structure of 4-critical triangle-free graphs embedded in a fixed surface.
Copyright Owner
Zdenek Dvorak and Bernard Lidicky
Copyright Date
2018
Language
en
File Format
application/pdf
Citation Information
Zdenek Dvorak and Bernard Lidicky. "Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains" SIAM Journal on Discrete Mathematics Vol. 32 Iss. 3 (2018) p. 1775 - 1805 Available at: http://works.bepress.com/bernard-lidicky/53/
This article is published as Dvorák, Zdenek, and Bernard Lidický. "Fine structure of 4-critical triangle-free graphs I. planar graphs with two triangles and 3-colorability of chains." SIAM Journal on Discrete Mathematics 32, no. 3 (2018): 1775-1805. doi: 10.1137/15M1023385. Posted with permission.