Other formats:
BibTeX
LaTeX
RIS
@article{1824820,
author = {Dvořák, Zdeněk and Kráľ, Daniel and Thomas, Robin},
article_location = {SAN DIEGO},
article_number = {September 2021},
doi = {http://dx.doi.org/10.1016/j.jctb.2020.04.006},
keywords = {Graph coloring; Planar graphs; Triangle-free graphs; Havel's problem},
language = {eng},
issn = {0095-8956},
journal = {Journal of Combinatorial Theory. Series B},
title = {Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies},
url = {http://dx.doi.org/10.1016/j.jctb.2020.04.006},
volume = {150},
year = {2021}
}
TY - JOUR
ID - 1824820
AU - Dvořák, Zdeněk - Kráľ, Daniel - Thomas, Robin
PY - 2021
TI - Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies
JF - Journal of Combinatorial Theory. Series B
VL - 150
IS - September 2021
SP - 244-269
EP - 244-269
PB - ACADEMIC PRESS INC ELSEVIER SCIENCE
SN - 00958956
KW - Graph coloring
KW - Planar graphs
KW - Triangle-free graphs
KW - Havel's problem
UR - http://dx.doi.org/10.1016/j.jctb.2020.04.006
N2 - 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.
ER -
DVOŘÁK, Zdeněk, Daniel KRÁĽ and Robin THOMAS. Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. \textit{Journal of Combinatorial Theory. Series B}. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2021, vol.~150, September 2021, p.~244-269. ISSN~0095-8956. Available from: https://dx.doi.org/10.1016/j.jctb.2020.04.006.
|
