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

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10437046" target="_blank" >RIV/00216208:11320/21:10437046 - isvavai.cz</a>
Alternative codes found
RIV/00216224:14330/21:00124669
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=IDlYpoIqBL" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=IDlYpoIqBL</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jctb.2020.04.006" target="_blank" >10.1016/j.jctb.2020.04.006</a>

Result language
angličtina
Original language name
Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies
Original language 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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)