Skip to main content
Article
Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles
SIAM Journal on Discrete Mathematics
  • Zdeněk Dvořák, Charles University
  • Bernard Lidicky, Iowa State University
Document Type
Article
Publication Version
Published Version
Publication Date
1-1-2017
DOI
10.1137/15M1023397
Abstract

We study 3-coloring properties of triangle-free planar graphs $G$ with two precolored 4-cycles $C_1$ and $C_2$ that are far apart. We prove that either every precoloring of $C_1\cup C_2$ extends to a 3-coloring of $G$, or $G$ contains one of two special substructures which uniquely determine which 3-colorings of $C_1\cup C_2$ extend. As a corollary, we prove that there exists a constant $D>0$ such that if $H$ is a planar triangle-free graph and if $S\subseteq V(H)$ consists of vertices at pairwise distances at least $D$, then every precoloring of $S$ extends to a 3-coloring of $H$. This gives a positive answer to a conjecture of Dvořák, Král', and Thomas, and implies an exponential lower bound on the number of 3-colorings of triangle-free planar graphs of bounded maximum degree.

Comments

This article is published as Dvorák, Zdenek, and Bernard Lidický. "Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles." SIAM Journal on Discrete Mathematics 31, no. 2 (2017): 865-874. doi: 10.1137/15M1023397. Posted with permission.

Copyright Owner
The Authors
Language
en
File Format
application/pdf
Citation Information
Zdeněk Dvořák and Bernard Lidicky. "Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles" SIAM Journal on Discrete Mathematics Vol. 31 Iss. 2 (2017) p. 865 - 874
Available at: http://works.bepress.com/bernard-lidicky/37/