Publication details
Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies
| Authors | |
|---|---|
| Year of publication | 2021 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Combinatorial Theory. Series B |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.1016/j.jctb.2020.04.006 |
| Doi | http://dx.doi.org/10.1016/j.jctb.2020.04.006 |
| Keywords | Graph coloring; Planar graphs; Triangle-free graphs; Havel's problem |
| Description | We settle a problem of Havel by showing that there exists an absolute constant d such that if G is a planar graph in which every two distinct triangles are at distance at least d, then G is 3-colorable. In fact, we prove a more general theorem. Let G be a planar graph, and let H be a set of connected subgraphs of G, each of bounded size, such that every two distinct members of H are at least a specified distance apart and all triangles of G are contained in boolean OR H. We give a sufficient condition for the existence of a 3-coloring phi of G such that for every H is an element of H the restriction of phi to H is constrained in a specified way. (C) 2020 Elsevier Inc. All rights reserved. |