Conflict-free chromatic number versus conflict-free chromatic index

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Conflict-free chromatic number versus conflict-free chromatic index
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)