Hardness results for total rainbow connection of graphs

DOI10.7151/DMGT.1856MaRDI QIDQ274688zbMATH OpenOpenAlexFDO

Authors Lily Chen, Bofeng Huo, Yingbin Ma

Publication date 25 April 2016

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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)

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.

Cites work

• Hardness and algorithms for rainbow connection
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• Note on the hardness of rainbow connections for planar and line graphs
• On rainbow connection
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• On the rainbow vertex-connection
• Rainbow connection in 3-connected graphs
• Rainbow connection in graphs
• Rainbow connection in graphs with minimum degree three
• Rainbow connections for outerplanar graphs with diameter 2 and 3
• Some simplified NP-complete graph problems
• 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
• Total rainbow \(k\)-connection in 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)