Structural parameterization for minimum conflict-free colouring

Abstract

Conflict-free q-colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the Minimum Conflict-free q-Colouring problem. Given a graph G and a fixed constant q, Minimum Conflict-free q-Colouring is to find a conflict-free q-colouring of G that minimizes the number of coloured vertices. We study the parameterized complexity of the Minimum Conflict-free q-Colouring problem when parameterized by structural parameters like treewidth and vertex cover of G. We give an FPT algorithm for Minimum Conflict-free q-Colouring parameterized by treewidth and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH). Using standard kernelization lower bound techniques, it is easy to see that Minimum Conflict-free q-Colouring parameterized by treewidth does not admit polynomial kernels. We extend this result for a larger parameter namely the vertex cover of G, when q > 1.