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

J 2021

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

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

Základní údaje

Originální název

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

Autoři

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

Vydání

Journal of Combinatorial Theory. Series B, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2021, 0095-8956

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 1.491

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/21:00124669

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

Graph coloring; Planar graphs; Triangle-free graphs; Havel's problem

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 23. 5. 2022 15:44, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Citovat

DVOŘÁK, Zdeněk; Daniel KRÁĽ a Robin THOMAS. Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. Journal of Combinatorial Theory. Series B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2021, roč. 150, September 2021, s. 244-269. ISSN 0095-8956. Dostupné z: https://doi.org/10.1016/j.jctb.2020.04.006.

@article{1824820,
   author = {Dvořák, Zdeněk and Kráľ, Daniel and Thomas, Robin},
   article_location = {SAN DIEGO},
   article_number = {September 2021},
   doi = {https://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ÁĽ a 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, roč.~150, September 2021, s.~244-269. ISSN~0095-8956. Dostupné z: https://doi.org/10.1016/j.jctb.2020.04.006.

Přehled o publikaci