Further hardness results on rainbow and strong rainbow connectivity

DOI10.1016/j.dam.2015.07.041zbMath1329.05171arXiv1404.3082OpenAlexW1920882336MaRDI QIDQ908308

Juho Lauri

Publication date: 4 February 2016

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

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

zbMATH Keywords

computational complexityrainbow connectivity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (8)

On finding rainbow and colorful paths ⋮ On the complexity of rainbow coloring problems ⋮ On the complexity of \(k\)-rainbow cycle colouring problems ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ Algorithm on rainbow connection for maximal outerplanar graphs ⋮ Rainbow connectivity of Moore cages of girth 6

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Hardness and algorithms for rainbow connection
• The complexity of determining the rainbow vertex-connection of a graph
• A simplified NP-complete satisfiability problem
• Rainbow connections of graphs: a survey
• Grad and classes with bounded expansion. I: Decompositions
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• New Hardness Results in Rainbow Connectivity
• New Races in Parameterized Algorithmics
• Inapproximability of Rainbow Colouring
• Rainbow connection in graphs
• 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
• On planar geodetic graphs
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Further hardness results on rainbow and strong rainbow connectivity