Asymptotically Optimal Proper Conflict-Free Colouring

Abstract

A proper conflict-free colouring of a graph is a colouring of the vertices such that any two adjacent vertices receive different colours, and for every non-isolated vertex $v$, some colour appears exactly once on the neighbourhood of $v$. Caro, Petruševski and Škrekovski conjectured that every connected graph with maximum degree $\Delta \ge 3$ has a proper conflict-free colouring with at most $\Delta +1$ colours. This conjecture holds for $\Delta =3$ and remains open for $\Delta \ge 4$. In this paper we prove that this conjecture holds asymptotically; namely, every graph with maximum degree $\Delta$ has a proper conflict-free colouring with $(1+o(1))\Delta$ colours.

References in corpus (5)

• Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods
• Linear colorings of subcubic graphs
• Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
• Proper Conflict-free Coloring of Graphs with Large Maximum Degree
• Odd colourings, conflict-free colourings and strong colouring numbers

Cited by in corpus (1)

• Boundedness for proper conflict-free and odd colorings