Campus Units

Mathematics

Document Type

Article

Publication Version

Published Version

Publication Date

2018

Journal or Book Title

SIAM Journal on Discrete Mathematics

Volume

32

Issue

1

First Page

94

Last Page

105

DOI

10.1137/15M1023403

Abstract

Dvořák, Král', and Thomas [Three-Coloring Triangle-Free Graphs on Surfaces IV. Bounding Face Sizes of 4-Critical Graphs, preprint, arXiv:1404.6356v3, 2015; Three-Coloring Triangle-Free Graphs on Surfaces VI. 3-Colorability of Quadrangulations, preprint, arXiv:1509.01013, 2015] 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 a plane with two precolored cycles) whose coloring properties are not entirely determined. In this paper, we fill these gaps.

Comments

This article is published as Dvorák, Zdenek, and Bernard Lidický. "Fine structure of 4-critical triangle-free graphs III. General surfaces." SIAM Journal on Discrete Mathematics 32, no. 1 (2018): 94-105. doi: 10.1137/15M1023403. Posted with permission.

Copyright Owner

Society for Industrial and Applied Mathematics

Language

en

File Format

application/pdf

Share

COinS