Fine structure of 4-critical triangle-free graphs I. Planar graphs with two triangles and 3-colorability of chains

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 that 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 followup papers to give detailed information about the structure of 4-critical triangle-free graphs embedded in a fixed surface.

38 pages, 6 figures; corrections from the review process

References in corpus (5)

• Planar 4-critical graphs with four triangles
• 3-coloring triangle-free planar graphs with a precolored 8-cycle
• 4-critical graphs on surfaces without contractible (<=4)-cycles
• Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles
• Fine structure of 4-critical triangle-free graphs III. General surfaces