Publication details

Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies



Year of publication 2021
Type Article in Periodical
Magazine / Source Journal of Combinatorial Theory. Series B
MU Faculty or unit

Faculty of Informatics

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.

You are running an old browser version. We recommend updating your browser to its latest version.

More info