Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385400" target="_blank" >RIV/00216208:11320/18:10385400 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1016/j.jctb.2017.09.001" target="_blank" >https://doi.org/10.1016/j.jctb.2017.09.001</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jctb.2017.09.001" target="_blank" >10.1016/j.jctb.2017.09.001</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
Popis výsledku v původním jazyce
We introduce a new variant of graph coloring called correspondence colming which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.
Název v anglickém jazyce
Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
Popis výsledku anglicky
We introduce a new variant of graph coloring called correspondence colming which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.

Projekt
<a href="/cs/project/GA14-19503S" target="_blank" >GA14-19503S: Barevnost a struktura grafů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2018
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)