Szczegóły publikacji
Opis bibliograficzny
A note on the conflict-free chromatic index / Mateusz KAMYCZURA, Mariusz MESZKA, Jakub PRZYBYŁO // Discrete Mathematics ; ISSN 0012-365X. — 2024 — vol. 347 iss. 4 art. no. 113897, s. 1–4. — Bibliogr. s. 4, Abstr. — Publikacja dostępna online od: 2024-01-23
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 152002 |
|---|---|
| Data dodania do BaDAP | 2024-04-04 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2024.113897 |
| Rok publikacji | 2024 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
Let G be a graph with maximum degree Δ and without isolated vertices. An edge colouring c of G is conflict-free if the closed neighbourhood of every edge includes a uniquely coloured element. The least number of colours admitting such c is the conflict-free chromatic index of G, denoted by χCF′(G). In Dębski and Przybyło (2022) [4] it was recently proved by means of the probabilistic method that χCF′(G)≤C1log2Δ+C2, where C1>337 and C2 are constants, whereas there are families of graphs with χCF′(G)≥(1−o(1))log2Δ. In this note we provide an explicit simple proof of the fact that χCF′(G)≤3log2Δ+1, which is a corollary of a stronger result: χCF′(G)≤3log2χ(G)+1. For this aim we prove a few auxiliary observations, implying in particular that χCF′(G)≤4 for every bipartite graph G.
