Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
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.