Heggernes, Pinar ;
Issac, Davis ;
Lauri, Juho ;
Lima, Paloma T. ;
van Leeuwen, Erik Jan
Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs
Abstract
Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertexconnected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertexconnected. Although edgecolorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question.
We show that the problem remains NPcomplete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertexconnected optimally in polynomial time.
BibTeX  Entry
@InProceedings{heggernes_et_al:LIPIcs:2018:9665,
author = {Pinar Heggernes and Davis Issac and Juho Lauri and Paloma T. Lima and Erik Jan van Leeuwen},
title = {{Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {83:183:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9665},
URN = {urn:nbn:de:0030drops96657},
doi = {10.4230/LIPIcs.MFCS.2018.83},
annote = {Keywords: Rainbow coloring, graph classes, polynomialtime algorithms, approximation algorithms}
}
2018
Keywords: 

Rainbow coloring, graph classes, polynomialtime algorithms, approximation algorithms 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

2018 