Algorithms for the rainbow vertex coloring problem on graph classes

DOI10.1016/J.TCS.2021.07.009OpenAlexW3186032444MaRDI QIDQ820548FDOQ820548

Authors 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

graph classespermutation graphsrainbow vertex coloringpowers of trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• Complexity of rainbow vertex connectivity problems for restricted graph classes
• Rainbow vertex coloring bipartite graphs and chordal graphs
• Further hardness results on the rainbow vertex-connection number of graphs

Cites work

• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• Further hardness results on the rainbow vertex-connection number of graphs
• Linear-time algorithms for tree root problems
• Modular decomposition and transitive orientation
• Rainbow connection in graphs
• Rainbow connection number and connected dominating sets
• Rainbow vertex coloring bipartite graphs and chordal graphs
• The complexity of determining the rainbow vertex-connection of a graph
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The strong rainbow vertex-connection of graphs

Cited in

(6)

• Algorithms for the rainbow vertex coloring problem on graph classes
• On the complexity of \(k\)-rainbow cycle colouring problems
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• Rainbow vertex coloring bipartite graphs and chordal graphs
• Revisiting a randomized algorithm for the minimum rainbow subgraph problem
• Complexity of rainbow vertex connectivity problems for restricted graph classes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820548)