Proper conflict-free colourings of graphs
Time: 14:00 -- Location: LRI, 445
summary: Given a graph \(G\) of maximum degree \(\Delta\), the proper colouring problem asks for the minimum number of colours that can be assigned to the vertices of \(G\) such that no pair of adjacent vertices are given the same colour; it is easy to show that at most \(\Delta+1\) colours are required. The proper conflict-free colouring problem has the same setting, but imposes an additional constraint: we must also ensure that every open neighbourhood contains at least one unique occurrence of some colour. Caro, Petruševski and Škrekovski conjectured that \(\Delta+1\) colours are sufficient if \(\Delta>2\). Liu and Reed recently proved that the conjecture holds asymptotically, by showing that at most \(\Delta + O(\Delta^{2/3} \log \Delta)\) colours are necessary. We improve their result by eliminating the polynomial factor in the second-order term, i.e. we show that at most \(\Delta + O(\log \Delta)\) colours are required.