From χ- to χ_p-bounded classes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10476568" target="_blank" >RIV/00216208:11320/23:10476568 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=shmtzq0fGl" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=shmtzq0fGl</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

From χ- to χ_p-bounded classes

Popis výsledku v původním jazyce

chi-bounded classes are studied here in the context of star colorings and, more generally, chi(p)-colorings. This fits to a general scheme of sparsity and leads to natural extensions of the notion of bounded expansion class. In this paper we solve two conjectures related to star coloring (i.e. chi(2)) boundedness. One of the conjectures is disproved and in fact we determine which weakening holds true. chi(p)-boundedness leads to more stability and we give structural characterizations of (strong and weak) chi(p)-bounded classes. We also generalize a result of Wood relating the chromatic number of a graph to the star chromatic number of its 1-subdivision. As an application of our characterizations, among other things, we show that for every odd integer g &gt; 3 even hole-free graphs G contain at most phi(g, omega(G)) |G| holes of length g. (c) 2021 Elsevier Inc. All rights reserved.

Název v anglickém jazyce

From χ- to χ_p-bounded classes

Popis výsledku anglicky

chi-bounded classes are studied here in the context of star colorings and, more generally, chi(p)-colorings. This fits to a general scheme of sparsity and leads to natural extensions of the notion of bounded expansion class. In this paper we solve two conjectures related to star coloring (i.e. chi(2)) boundedness. One of the conjectures is disproved and in fact we determine which weakening holds true. chi(p)-boundedness leads to more stability and we give structural characterizations of (strong and weak) chi(p)-bounded classes. We also generalize a result of Wood relating the chromatic number of a graph to the star chromatic number of its 1-subdivision. As an application of our characterizations, among other things, we show that for every odd integer g &gt; 3 even hole-free graphs G contain at most phi(g, omega(G)) |G| holes of length g. (c) 2021 Elsevier Inc. All rights reserved.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

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

1096-0902

Svazek periodika

158

Číslo periodika v rámci svazku

Part 1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

24

Strana od-do

186-209

Kód UT WoS článku

000901805500008

EID výsledku v databázi Scopus

2-s2.0-85108556243