Towards a complexity dichotomy for colourful components problems on k-caterpillars and small-degree planar graphs

Janka Chlebikova, Clément Dallard

Research output: Chapter in Book/Report/Conference proceedingConference contribution

58 Downloads (Pure)

Abstract

A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours, and a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph, the Colourful Components problem asks whether there exist at most p edges whose removal makes the graph colourful, and the Colourful Partition problem asks whether there exists a partition of the vertex set with at most p parts such that each part induces a colourful component. We study the problems on k-caterpillars (caterpillars with hairs of length at most k) and explore the boundary between polynomial and NP-complete cases. It is known that the problems are NP-complete on 2-caterpillars with unbounded maximum degree. We prove that both problems remain NP-complete on binary 4-caterpillars and on ternary 3-caterpillars. This answers an open question regarding the complexity of the problems on trees with maximum degree at most 5. On the positive side, we give a linear time algorithm for 1-caterpillars with unbounded degree, even if the backbone is a cycle, which outperforms the previous best complexity for paths and widens the class of graphs. Finally, we answer an open question regarding the complexity of Colourful Components on graphs with maximum degree at most 5. We show that the problem is NP-complete on 5-coloured planar graphs with maximum degree 4, and on 12-coloured planar graphs with maximum degree 3. Since the problem can be solved in polynomial-time on graphs with maximum degree 2, the results are the best possible with regard to the maximum degree.
Original languageEnglish
Title of host publicationCombinatorial Algorithms
Subtitle of host publication30th International Workshop, IWOCA 2019, Pisa, Italy, July 23–25, 2019, Proceedings
EditorsC. Colbourn, R. Grossi, N. Pisanti
PublisherSpringer
Pages136-147
Number of pages12
ISBN (Electronic)978-3-030-25005-8
ISBN (Print)978-3-030-25004-1
DOIs
Publication statusPublished - 10 Jul 2019
Event30th International Workshop on Combinatorial Algorithms IWOCA 2019 - Pisa, Italy
Duration: 23 Jul 201925 Jul 2019

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11638
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference30th International Workshop on Combinatorial Algorithms IWOCA 2019
Country/TerritoryItaly
CityPisa
Period23/07/1925/07/19

Keywords

  • colourful component
  • caterpillar
  • binary tree
  • planar subcubic graph

Fingerprint

Dive into the research topics of 'Towards a complexity dichotomy for colourful components problems on <i>k</i>-caterpillars and small-degree planar graphs'. Together they form a unique fingerprint.

Cite this