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

3

First Page

1775

Last Page

1805

DOI

10.1137/15M1023385

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.

Comments

This article is published as Dvorák, Zdenek, and Bernard Lidický. "Fine structure of 4-critical triangle-free graphs I. planar graphs with two triangles and 3-colorability of chains." SIAM Journal on Discrete Mathematics 32, no. 3 (2018): 1775-1805. doi: 10.1137/15M1023385. Posted with permission.

Copyright Owner

Zdenek Dvorak and Bernard Lidicky

Language

en

File Format

application/pdf

Share

COinS