Abstract: A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph $G$ and an integer $p$, the Colourful Components problem asks whether there exist at most $p$ edges whose removal makes $G$ colourful and the Colourful Partition problem asks whether there exists a partition of $G$ into at most $p$ colourful components. In order to refine our understanding of the complexity of the probl...
(read more)
Topics: 
Combinatorics
Discrete mathematics