Szczegóły publikacji
Opis bibliograficzny
On conflict-free proper colourings of graphs without small degree vertices / Mateusz KAMYCZURA, Jakub PRZYBYŁO // Discrete Mathematics ; ISSN 0012-365X. — 2024 — vol. 347 iss. 1 art. no. 113712, s. 1–6. — Bibliogr. s. 6, Abstr. — Publikacja dostępna online od: 2023-10-04
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 151023 |
|---|---|
| Data dodania do BaDAP | 2024-01-03 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2023.113712 |
| Rok publikacji | 2024 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Discrete Mathematics |
Abstract
A proper vertex colouring of a graph G is conflict-free if in the neighbourhood of every vertex some colour appears exactly once, while it is called h-conflict-free if there are at least h such colours for each vertex of G. The least numbers of colours in such colourings of G are denoted by χpcf(G) and χpcfh(G), respectively. The latter parameter may be regarded as a natural relaxation of the 2-chromatic number, χ2(G), i.e. the least number of colours in a proper colouring of the square of a given graph G. It is known that χpcfh(G) can be as large as (h+1)(Δ+1)≈Δ2 for graphs with maximum degree Δ and h very close to Δ. We provide several new upper bounds for these parameters for graphs with minimum degrees δ large enough and h of smaller order than δ. In particular, we show that χpcfh(G)⩽(1+o(1))Δ if δ≫lnΔ and h≪δ, and that χpcf(G)⩽Δ+O(lnΔ) for regular graphs. These are related with the conjecture of Caro, Petruševski and Škrekovski that χpcf(G)⩽Δ+1 for every connected graph G of maximum degree Δ⩾3, towards which they proved that [Formula presented] if Δ⩾1. © 2023 The Author(s)
