Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385412" target="_blank" >RIV/00216208:11320/18:10385412 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1016/j.jctb.2018.03.001" target="_blank" >https://doi.org/10.1016/j.jctb.2018.03.001</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jctb.2018.03.001" target="_blank" >10.1016/j.jctb.2018.03.001</a>

Result language
angličtina
Original language name
Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk
Original language description
Let G be a plane graph of girth at least five. We show that if there exists a 3-coloring Phi of a cycle C of G that does not extend to a 3-coloring of G, then G has a subgraph H on O(|C|) vertices that also has no 3-coloring extending Phi. This is asymptotically best possible and improves a previous bound of Thomassen. In the next paper of the series we will use this result and the attendant theory to prove a generalization to graphs on surfaces with several precolored cycles.
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
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)