License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.83
URN: urn:nbn:de:0030-drops-96657
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9665/
Go to the corresponding LIPIcs Volume Portal

Heggernes, Pinar ; Issac, Davis ; Lauri, Juho ; Lima, Paloma T. ; van Leeuwen, Erik Jan

Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

pdf-format:
LIPIcs-MFCS-2018-83.pdf (0.5 MB)

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 vertex-connected 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 vertex-connected. Although edge-colorings 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 NP-complete 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 vertex-connected 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:1--83:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9665},
  URN =		{urn:nbn:de:0030-drops-96657},
  doi =		{10.4230/LIPIcs.MFCS.2018.83},
  annote =	{Keywords: Rainbow coloring, graph classes, polynomial-time algorithms, approximation algorithms}
}

Keywords: Rainbow coloring, graph classes, polynomial-time algorithms, approximation algorithms
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI