Colourful components in k-caterpillars and planar graphs

Janka Chlebikova, Clément Dallard

Research output: Contribution to journalArticlepeer-review

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 problems on trees, we study both problems on k-caterpillars, which are trees with a central path P such that every vertex not in P is within distance k from a vertex in P. We prove that Colourful Components and Colourful Partition are NP-complete on 4-caterpillars with maximum degree 3, 3-caterpillars with maximum degree 4 and 2-caterpillars with maximum degree 5. On the other hand, we show that the problems are linear-time solvable on 1-caterpillars. Hence, our results imply two complexity dichotomies on trees: Colourful Components and Colourful Partition are linear-time solvable on trees with maximum degree d if d ≤ 2 (that is, on paths), and NP-complete otherwise; Colourful Components and Colourful Partition are linear-time solvable on k-caterpillars if k ≤ 1, and NP-complete otherwise. We leave three open cases which, if solved, would provide a complexity dichotomy for both problems on k-caterpillars, for every non-negative integer k, with respect to the maximum degree. We also show that Colourful Components is NP-complete on 5-coloured planar graphs with maximum degree 4 and on 12-coloured planar graphs with maximum degree~3. Our results answer two open questions of Bulteau et al. mentioned in [30th Annual Symposium on Combinatorial Pattern Matching, 2019].
Original languageEnglish
Pages (from-to)137-150
Number of pages14
JournalTheoretical Computer Science
Volume895
Early online date5 Oct 2021
DOIs
Publication statusPublished - 4 Dec 2021

Keywords

  • colorful component
  • trees
  • planar graphs
  • NP-complete
  • linear-time algorithm

Fingerprint

Dive into the research topics of 'Colourful components in k-caterpillars and planar graphs'. Together they form a unique fingerprint.

Cite this