Conflict-free chromatic number versus conflict-free chromatic index
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F22%3A00128975" target="_blank" >RIV/00216224:14330/22:00128975 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1002/jgt.22743" target="_blank" >https://doi.org/10.1002/jgt.22743</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/jgt.22743" target="_blank" >10.1002/jgt.22743</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Conflict-free chromatic number versus conflict-free chromatic index
Popis výsledku v původním jazyce
A vertex coloring of a given graph G is conflict-free if the closed neighborhood of every vertex contains a unique color (i.e., a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict-free chromatic number of G, denoted chi CF(G). What is the maximum possible conflict-free chromatic number of a graph with a given maximum degree Delta? Trivially, chi CF(G)<=chi(G)<=Delta+1, but it is far from optimal-due to results of Glebov, Szabo, and Tardos, and of Bhyravarapu, Kalyanasundaram, and Mathew, the answer is known to be Theta(ln2 Delta). We show that the answer to the same question in the class of line graphs is Theta(ln Delta)-it follows that the extremal value of the conflict-free chromatic index among graphs with maximum degree Delta is much smaller than the one for conflict-free chromatic number. The same result for chi CF(G) is also provided in the class of near regular graphs, that is, graphs with minimum degree delta >=alpha Delta.
Název v anglickém jazyce
Conflict-free chromatic number versus conflict-free chromatic index
Popis výsledku anglicky
A vertex coloring of a given graph G is conflict-free if the closed neighborhood of every vertex contains a unique color (i.e., a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict-free chromatic number of G, denoted chi CF(G). What is the maximum possible conflict-free chromatic number of a graph with a given maximum degree Delta? Trivially, chi CF(G)<=chi(G)<=Delta+1, but it is far from optimal-due to results of Glebov, Szabo, and Tardos, and of Bhyravarapu, Kalyanasundaram, and Mathew, the answer is known to be Theta(ln2 Delta). We show that the answer to the same question in the class of line graphs is Theta(ln Delta)-it follows that the extremal value of the conflict-free chromatic index among graphs with maximum degree Delta is much smaller than the one for conflict-free chromatic number. The same result for chi CF(G) is also provided in the class of near regular graphs, that is, graphs with minimum degree delta >=alpha Delta.
Klasifikace
Druh
J<sub>imp</sub> - Č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)
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2022
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
Journal of Graph Theory
ISSN
0364-9024
e-ISSN
—
Svazek periodika
99
Číslo periodika v rámci svazku
3
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
10
Strana od-do
349-358
Kód UT WoS článku
000698588900001
EID výsledku v databázi Scopus
2-s2.0-85115402694