5-list-coloring planar graphs with distant precolored vertices

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10364949" target="_blank" >RIV/00216208:11320/17:10364949 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.jctb.2016.06.006" target="_blank" >http://dx.doi.org/10.1016/j.jctb.2016.06.006</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jctb.2016.06.006" target="_blank" >10.1016/j.jctb.2016.06.006</a>

Jazyk výsledku

angličtina

Název v původním jazyce

5-list-coloring planar graphs with distant precolored vertices

Popis výsledku v původním jazyce

We answer positively the question of Albertson asking whether every planar graph can be 5-list-colored even if it contains precolored vertices, as long as they are sufficiently far apart from each other. In order to prove this claim, we also give bounds on the sizes of graphs critical with respect to 5-list coloring. In particular, if G is a planar graph, H is a connected subgraph of G and L is an assignment of lists of colors to the vertices of G such that vertical bar L(v)vertical bar &gt;= 5 for every v is an element of V(G)V(H) and G is not L-colorable, then G contains a subgraph with O(vertical bar H vertical bar(2)) vertices that is not L-colorable.

Název v anglickém jazyce

5-list-coloring planar graphs with distant precolored vertices

Popis výsledku anglicky

We answer positively the question of Albertson asking whether every planar graph can be 5-list-colored even if it contains precolored vertices, as long as they are sufficiently far apart from each other. In order to prove this claim, we also give bounds on the sizes of graphs critical with respect to 5-list coloring. In particular, if G is a planar graph, H is a connected subgraph of G and L is an assignment of lists of colors to the vertices of G such that vertical bar L(v)vertical bar &gt;= 5 for every v is an element of V(G)V(H) and G is not L-colorable, then G contains a subgraph with O(vertical bar H vertical bar(2)) vertices that is not L-colorable.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

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ů

Název periodika

Journal of Combinatorial Theory. Series B

ISSN

0095-8956

e-ISSN

—

Svazek periodika

122

Číslo periodika v rámci svazku

january

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

42

Strana od-do

311-352

Kód UT WoS článku

000389788300015

EID výsledku v databázi Scopus

—