Rainbow connection in 3-connected graphs

DOI10.1007/S00373-012-1204-9zbMATH Open1272.05053arXiv1010.6131OpenAlexW2137874848MaRDI QIDQ367069FDOQ367069

Authors: Yongtang Shi, Xueliang Li 

Publication date: 26 September 2013

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

Abstract: An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper, we proved that $rc(G)leq3(n+1)/5$ for all $3$-connected graphs.

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

Recommendations

• scientific article; zbMATH DE number 6837036
• Rainbow connection in graphs with minimum degree three
• Rainbow connection number two and clique number
• Rainbow connection number of dense graphs
• Rainbow connection number and connectivity

zbMATH Keywords

connectivityrainbow connectionfan lemma

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• On rainbow connection
• Rainbow connection number and connected dominating sets
• Rainbow connection in graphs
• Hardness and algorithms for rainbow connection
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Rainbow connection in graphs with minimum degree three

Cited In (41)

• Generalized rainbow connection of graphs
• Bounds for the rainbow connection number of graphs
• Rainbow connection number of graphs with diameter 3
• Hardness results for total rainbow connection of graphs
• Rainbow connections for outerplanar graphs with diameter 2 and 3
• Coupon coloring of cographs
• Rainbow connection number, bridges and radius
• Rainbow connection number and connectivity
• Upper bounds of proper connection number of graphs
• Finite families of forbidden subgraphs for rainbow connection in graphs
• (Strong) rainbow connection on the splitting of 3-path
• Nordhaus-Gaddum-type theorem for rainbow connection number of graphs
• Graphs with small total rainbow connection number
• Rainbow connection in graphs with minimum degree three
• The generalized 3-connectivity of star graphs and bubble-sort graphs
• Characterize graphs with rainbow connection numbers \(m-2\) and \(m-3\)
• Injective coloring of some graph operations
• Note on the hardness of rainbow connections for planar and line graphs
• Rainbow connection for some families of hypergraphs
• The vertex-rainbow connection number of some graph operations
• Rainbow \(k\)-connection in dense graphs (extended abstract)
• Rainbow connectivity of Moore cages of girth 6
• Long rainbow paths and rainbow cycles in edge colored graphs. A survey
• Rainbow connection in graphs
• Rainbow connection number two and clique number
• Rainbow connection numbers of middle and total graphs
• The complexity of determining the vertex-rainbow index of graphs
• Rainbow connection in some digraphs
• Rainbow connectivity of linear polygon chains
• Upper bounds for the rainbow connection numbers of line graphs
• Coupon coloring of some special graphs
• On 2-rainbow domination of generalized Petersen graphs
• Graphs with (strong) proper connection numbers \(m - 3\) and \(m - 4\)
• Rainbow and monochromatic vertex-connection of random graphs
• Proper connection numbers of complementary graphs
• Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs
• Generalized rainbow connection of graphs and their complements
• Strong rainbow coloring of unicyclic graphs
• Proper connection number and connected dominating sets
• Rainbow connection numbers of line graphs.
• Color-connected graphs and information-transfer paths

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

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