Informace o publikaci

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


DVOŘÁK Zdeněk KRÁĽ Daniel THOMAS Robin

Rok publikování 2021
Druh Článek v odborném periodiku
Časopis / Zdroj Journal of Combinatorial Theory. Series B
Fakulta / Pracoviště MU

Fakulta informatiky

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.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info