Hardness results for total rainbow connection of graphs

DOI10.7151/DMGT.1856zbMath1338.05077OpenAlexW2312938749MaRDI QIDQ274688

Yingbin Ma, Bofeng Huo, Lily Chen

Publication date: 25 April 2016

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.1856

zbMATH Keywords

computational complexitytotal rainbow connection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items (5)

Some results on the 3-total-rainbow index ⋮ Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number ⋮ Hardness result for the total rainbow \(k\)-connection of graphs ⋮ Rainbow connections in digraphs ⋮ Total rainbow connection numbers of some special graphs

Cites Work

• Rainbow connections for outerplanar graphs with diameter 2 and 3
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• Rainbow connection in 3-connected graphs
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Total rainbow \(k\)-connection in graphs
• Hardness and algorithms for rainbow connection
• The complexity of determining the rainbow vertex-connection of a graph
• On rainbow connection
• Some simplified NP-complete graph problems
• Rainbow connections of graphs: a survey
• Note on the hardness of rainbow connections for planar and line graphs
• On the rainbow vertex-connection
• Rainbow connection in graphs
• Rainbow Connection in Graphs with Minimum Degree Three
• 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: Hardness results for total rainbow connection of graphs