Tampere University of Technology

TUTCRIS Research Portal

On the Complexity of Rainbow Coloring Problems

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Details

Original languageEnglish
Title of host publicationCombinatorial Algorithms
Subtitle of host publication26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers
EditorsZsuzsanna Lipták, William F. Smyth
PublisherSpringer International Publishing
Pages209-220
Number of pages12
ISBN (Electronic)978-3-319-29516-9
ISBN (Print)978-3-319-29515-2
DOIs
Publication statusPublished - 20 Feb 2016
Publication typeA4 Article in a conference publication
EventINTERNATIONAL WORKSHOP ON COMBINATORIAL ALGORITHMS -
Duration: 1 Jan 1900 → …

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9538
ISSN (Print)0302-9743

Conference

ConferenceINTERNATIONAL WORKSHOP ON COMBINATORIAL ALGORITHMS
Period1/01/00 → …

Abstract

An edge-colored graph G is said to be rainbow connected if between each pair of vertices there exists a path which uses each color at most once. The rainbow connection number, denoted by rc(G), is the minimum number of colors needed to make G rainbow connected. Along with its variants, which consider vertex colorings and/or so-called strong colorings, the rainbow connection number has been studied from both the algorithmic and graph-theoretic points of view.

In this paper we present a range of new results on the computational complexity of computing the four major variants of the rainbow connection number. In particular, we prove that the Strong Rainbow Vertex Coloring problem is NP-complete even on graphs of diameter 3. We show that when the number of colors is fixed, then all of the considered problems can be solved in linear time on graphs of bounded treewidth. Moreover, we provide a linear-time algorithm which decides whether it is possible to obtain a rainbow coloring by saving a fixed number of colors from a trivial upper bound. Finally, we give a linear-time algorithm for computing the exact rainbow connection numbers for three variants of the problem on graphs of bounded vertex cover number.

Publication forum classification

Field of science, Statistics Finland