Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains
Zdenĕk Dvořák, Bernard Lidický · Iowa State University Digital Repository (Iowa State University) · 2018
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.