Hardness results for total rainbow connection of graphs

DOI10.7151/DMGT.1856zbMATH Open1338.05077OpenAlexW2312938749MaRDI QIDQ274688FDOQ274688

Authors: Lily Chen, Bofeng Huo, Yingbin Ma 

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

Recommendations

• Hardness result for the total rainbow \(k\)-connection of graphs
• On total rainbow \(k\)-connected graphs
• The total-rainbow \(k\)-connection of 2-connected graphs.
• Graphs with small total rainbow connection number
• Some upper bounds for the total-rainbow connection number of graphs.

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)

Cites Work

• On rainbow connection
• Note on the hardness of rainbow connections for planar and line graphs
• Rainbow connection in graphs
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Hardness and algorithms for rainbow connection
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The complexity of determining the rainbow vertex-connection of a graph
• Some simplified NP-complete graph problems
• Rainbow connections for outerplanar graphs with diameter 2 and 3
• On the rainbow vertex-connection
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• Rainbow connection in graphs with minimum degree three
• Rainbow connection in 3-connected graphs
• Total rainbow \(k\)-connection in graphs
• The strong rainbow vertex-connection of graphs

Cited In (8)

• Hardness result for the total rainbow \(k\)-connection of graphs
• Rainbow connections in digraphs
• Hardness and Algorithms for Rainbow Connectivity
• Some results on the 3-total-rainbow index
• Graphs with small total rainbow connection number
• Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number
• Note on the hardness of rainbow connections for planar and line graphs
• Total rainbow connection numbers of some special graphs

This page was built for publication: Hardness results for total rainbow connection of graphs

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