Algorithms for the rainbow vertex coloring problem on graph classes

DOI10.1016/j.tcs.2021.07.009OpenAlexW3186032444MaRDI QIDQ820548

Paloma T. Lima, Erik Jan van Leeuwen, Marieke van der Wegen

Publication date: 27 September 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.03108

zbMATH Keywords

permutation graphsgraph classesrainbow vertex coloringpowers of trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Further hardness results on the rainbow vertex-connection number of graphs
• The complexity of determining the rainbow vertex-connection of a graph
• Modular decomposition and transitive orientation
• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• On the complexity of rainbow coloring problems
• Rainbow connections of graphs: a survey
• Linear-time algorithms for tree root problems
• Rainbow connection number and connected dominating sets
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Rainbow connection in graphs
• Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The strong rainbow vertex-connection of graphs

This page was built for publication: Algorithms for the rainbow vertex coloring problem on graph classes