Fine structure of 4-critical triangle-free graphs III. General surfaces

Abstract

Dvořák, Král' and Thomas 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 plane with two precolored cycles) whose coloring properties are not entirely determined. In this paper, we fill these gaps.

15 pages, 1 figure; corrections from the review process. arXiv admin note: text overlap with arXiv:1509.01013

References in corpus (2)

• Planar 4-critical graphs with four triangles
• Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles

Cited by in corpus (1)

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