Rainbow and monochromatic vertex-connection of random graphs

DOI10.1007/s10255-022-1027-2MaRDI QIDQ2087672

Wen-Jing Li, Hui Jiang, Jia-bei He

Publication date: 21 October 2022

Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10255-022-1027-2

zbMATH Keywords

graph coloring; random graphs; threshold function; rainbow vertex-connection number; monochromatic vertex-connection number

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C15: Coloring of graphs and hypergraphs

05C40: Connectivity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rainbow connection in 3-connected graphs
• On rainbow-\(k\)-connectivity of random graphs
• Hardness and algorithms for rainbow connection
• The complexity of determining the rainbow vertex-connection of a graph
• Extremal graphs with maximum monochromatic connectivity
• On rainbow connection
• Threshold functions
• More on the colorful monochromatic connectivity
• Some extremal results on the colorful monochromatic vertex-connectivity of a graph
• Rainbow connections of graphs: a survey
• The (vertex-)monochromatic index of a graph
• Hardness results for three kinds of colored connections of graphs
• Colorful monochromatic connectivity
• Rainbow connection number and connected dominating sets
• Properties of almost all graphs and complexes
• Rainbow connection in graphs
• Rainbow Connection of Random Regular Graphs
• The Diameter of Random Graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• THE MAXIMUM CONNECTIVITY OF A GRAPH
• Spanning trees with many leaves