2022/12/17 by Kamyczura, Mateusz, Przybyło, Jakub · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2212.08936
A proper vertex colouring of a graph G is referred to as 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 χ\rm pcf(G) and χ\rm pcfh(G), respectively. It is known that χ\rm 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 detached from δ. In particular we show that χ\rm pcfh(G)≤ (1+o(1))Δ if δ≫lnΔ and h≪ δ, and that χ\rm pcf(G)≤ Δ+O(ln Δ) for regular graphs. These specifically refer to the conjecture of Caro, Petruševski and Škrekovski that χ\rm pcf(G)≤ Δ+1 for every connected graph G of maximum degree Δ≥ 3, towards which they proved that χ\rm pcf(G)≤ \lfloor(5Δ)/(2)\rfloor if Δ≥ 1.