(3a:a)-List-Colorability of Embedded Graphs of Girth at Least Five
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10416998" target="_blank" >RIV/00216208:11320/20:10416998 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=qbQNCkCI~_" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=qbQNCkCI~_</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/18M1214056" target="_blank" >10.1137/18M1214056</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
(3a:a)-List-Colorability of Embedded Graphs of Girth at Least Five
Popis výsledku v původním jazyce
A graph G is list (b : a)-colorable if for every assignment of lists of size b to vertices of G there exists a choice of an a-element subset of the list at each vertex such that the subsets chosen at adjacent vertices are disjoint. We prove that for every positive integer a, the family of minimal obstructions of girth at least five to list (3a : a)-colorability is strongly hyperbolic, in the sense of the hyperbolicity theory developed by Postle and Thomas. This has a number of consequences; e.g., if a graph of girth at least five and Euler genus g is not list (3a : a)-colorable, then G contains a subgraph with O(g) vertices which is not list (3a : a)-colorable.
Název v anglickém jazyce
(3a:a)-List-Colorability of Embedded Graphs of Girth at Least Five
Popis výsledku anglicky
A graph G is list (b : a)-colorable if for every assignment of lists of size b to vertices of G there exists a choice of an a-element subset of the list at each vertex such that the subsets chosen at adjacent vertices are disjoint. We prove that for every positive integer a, the family of minimal obstructions of girth at least five to list (3a : a)-colorability is strongly hyperbolic, in the sense of the hyperbolicity theory developed by Postle and Thomas. This has a number of consequences; e.g., if a graph of girth at least five and Euler genus g is not list (3a : a)-colorable, then G contains a subgraph with O(g) vertices which is not list (3a : a)-colorable.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GA17-04611S" target="_blank" >GA17-04611S: Ramseyovské aspekty barvení grafů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2020
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ů
Údaje specifické pro druh výsledku
Název periodika
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
—
Svazek periodika
34
Číslo periodika v rámci svazku
4
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
29
Strana od-do
2137-2165
Kód UT WoS článku
000600645000007
EID výsledku v databázi Scopus
2-s2.0-85096355829