Complexity of rainbow vertex connectivity problems for restricted graph classes

DOI10.1016/j.dam.2016.11.023zbMath1354.05049arXiv1612.07768OpenAlexW2566896946MaRDI QIDQ505435

Juho Lauri

Publication date: 23 January 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityrainbow connectivity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items

Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Fundamentals of parameterized complexity
• Further hardness results on the rainbow vertex-connection number of graphs
• Rainbow connection in oriented graphs
• Hardness and algorithms for rainbow connection
• The complexity of determining the rainbow vertex-connection of a graph
• A simplified NP-complete satisfiability problem
• Further hardness results on rainbow and strong rainbow connectivity
• Bigeodetic graphs
• A partial k-arboretum of graphs with bounded treewidth
• On the complexity of rainbow coloring problems
• Rainbow connections of graphs: a survey
• Topology of series-parallel networks
• Grad and classes with bounded expansion. I: Decompositions
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• New Races in Parameterized Algorithmics
• Rainbow connection in graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The strong rainbow vertex-connection of graphs
• Parameterized Algorithms
• On planar geodetic graphs
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Complexity of rainbow vertex connectivity problems for restricted graph classes