FINE STRUCTURE OF 4-CRITICAL TRIANGLE-FREE GRAPHS I. PLANAR GRAPHS WITH TWO TRIANGLES AND 3-COLORABILITY OF CHAINS
2018
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.