FINE STRUCTURE OF 4-CRITICAL TRIANGLE-FREE GRAPHS II. PLANAR TRIANGLE-FREE GRAPHS WITH TWO PRECOLORED 4-CYCLES
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 boolean OR 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 boolean OR 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 subset of 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 Dvorak, Kral, and Thomas, and implies an exponential lower bound on the number of 3-colorings of triangle-free planar graphs of bounded maximum degree.