Szczegóły publikacji
Opis bibliograficzny
On asymptotically tight bound for the conflict-free chromatic index of nearly regular graphs / Mateusz KAMYCZURA, Jakub PRZYBYŁO // Discrete Mathematics ; ISSN 0012-365X . — 2026 — vol. 349 iss. 4 art. no. 114945, s. 1-9. — Bibliogr. s. 9, Abstr. — Publikacja dostępna online od: 2025-12-15
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 165466 |
|---|---|
| Data dodania do BaDAP | 2026-01-20 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2025.114945 |
| Rok publikacji | 2026 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
Let G be a graph of maximum degree Δ which does not contain isolated vertices. An edge coloring c of G is called conflict-free if each edge's closed neighborhood includes a uniquely colored element. The least number of colors admitting such c is called the conflict-free chromatic index of G and denoted . It is known that in general , while there is a family of graphs, e.g. the complete graphs, for which . In the present paper we provide the asymptotically tight upper bound for regular and nearly regular graphs, which in particular implies that the same bound holds a.a.s. for a random graph whenever for any fixed constant . Our proof is probabilistic and exploits classic results of Hall and Berge. This was inspired by our approach utilized in the particular case of complete graphs, for which we give a more specific upper bound.
