On rainbow-\(k\)-connectivity of random graphs

DOI10.1016/j.ipl.2012.01.014zbMath1243.05218arXiv1012.1942OpenAlexW2963274424MaRDI QIDQ436344

Hongyu Liang, Jing (Selena) He

Publication date: 20 July 2012

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsprobabilistic methodrandom graphrainbow connectivitysharp threshold function

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items (16)

Rainbow Connection of Random Regular Graphs ⋮ Rainbow colouring of split graphs ⋮ More on the colorful monochromatic connectivity ⋮ Rainbow connectivity and rainbow index of inhomogeneous random graphs ⋮ Conflict-free connection number of random graphs ⋮ Rainbow connections of graphs: a survey ⋮ Proper connection number of random graphs ⋮ Concentration of rainbow \(k\)-connectivity of a multiplex random graph ⋮ Unnamed Item ⋮ Rainbow \(k\)-connectivity of random bipartite graphs ⋮ Rainbow 2-connection numbers of Cayley graphs ⋮ On the threshold for rainbow connection number \(r\) in random graphs ⋮ The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths ⋮ Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph ⋮ Rainbow and monochromatic vertex-connection of random graphs ⋮ Pattern Colored Hamilton Cycles in Random Graphs

Cites Work

• On rainbow connection
• Threshold functions
• The rainbow connectivity of a graph
• Rainbow connection in graphs
• The Diameter of Random Graphs
• Every monotone graph property has a sharp threshold
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Hardness and Algorithms for Rainbow Connectivity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On rainbow-\(k\)-connectivity of random graphs