Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

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

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


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.
Original languageEnglish
Title of host publication43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK
EditorsIgor Potapov, Paul Spirakis, James Worrell
Number of pages13
Publication statusPublished - 2018


  • Rainbow coloring
  • graph classes
  • polynomial-time algorithms
  • approximation algorithms


Dive into the research topics of 'Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs'. Together they form a unique fingerprint.

Cite this