Informace o publikaci
Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies
| Autoři | |
|---|---|
| Rok publikování | 2021 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Combinatorial Theory. Series B |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1016/j.jctb.2020.04.006 |
| Doi | http://dx.doi.org/10.1016/j.jctb.2020.04.006 |
| Klíčová slova | Graph coloring; Planar graphs; Triangle-free graphs; Havel's problem |
| Popis | 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. |