Rainbow connection in 3-connected graphs

DOI10.1007/s00373-012-1204-9zbMath1272.05053arXiv1010.6131OpenAlexW2137874848MaRDI QIDQ367069

Yongtang Shi, Xue Liang Li

Publication date: 26 September 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

connectivityrainbow connectionfan lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items (25)

Hardness results for total rainbow connection of graphs ⋮ Rainbow connections for outerplanar graphs with diameter 2 and 3 ⋮ Injective coloring of some graph operations ⋮ Graphs with small total rainbow connection number ⋮ Upper bounds of proper connection number of graphs ⋮ Unnamed Item ⋮ Long rainbow paths and rainbow cycles in edge colored graphs. A survey ⋮ Proper connection number and connected dominating sets ⋮ Rainbow connections of graphs: a survey ⋮ Graphs with (strong) proper connection numbers \(m - 3\) and \(m - 4\) ⋮ Generalized rainbow connection of graphs and their complements ⋮ On 2-rainbow domination of generalized Petersen graphs ⋮ The vertex-rainbow connection number of some graph operations ⋮ Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs ⋮ The generalized 3-connectivity of star graphs and bubble-sort graphs ⋮ Coupon coloring of cographs ⋮ Generalized rainbow connection of graphs ⋮ Rainbow connection in some digraphs ⋮ Coupon coloring of some special graphs ⋮ Unnamed Item ⋮ The complexity of determining the vertex-rainbow index of graphs ⋮ Proper connection numbers of complementary graphs ⋮ Rainbow connectivity of Moore cages of girth 6 ⋮ Rainbow and monochromatic vertex-connection of random graphs ⋮ Note on the hardness of rainbow connections for planar and line graphs

Cites Work

• Unnamed Item
• Hardness and algorithms for rainbow connection
• On rainbow connection
• Rainbow connections of graphs: a survey
• Rainbow connection number and connected dominating sets
• 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

This page was built for publication: Rainbow connection in 3-connected graphs