Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes

DOI10.4230/LIPIcs.MFCS.2020.63OpenAlexW3082078513MaRDI QIDQ5089235

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

Publication date: 18 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12733/pdf/LIPIcs-MFCS-2020-63.pdf/

zbMATH Keywords

permutation graphsrainbow vertex coloringpowers of trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Algorithms for the rainbow vertex coloring problem on graph classes

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
• 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
• 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