Szczegóły publikacji
Opis bibliograficzny
Conflict-free chromatic number versus conflict-free chromatic index / Michał Dębski, Jakub PRZYBYŁO // Journal of Graph Theory ; ISSN 0364-9024. — 2022 — vol. 99 iss. 3, s. 349–358. — Bibliogr. s. 357–358, Abstr. — Publikacja dostępna online od: 2021-09-24
Autorzy (2)
- Dębski Michał
- AGHPrzybyło Jakub
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 139598 |
|---|---|
| Data dodania do BaDAP | 2022-03-23 |
| Tekst źródłowy | URL |
| DOI | 10.1002/jgt.22743 |
| Rok publikacji | 2022 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Journal of Graph Theory |
Abstract
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.
