Random regular graphs of high degree

DOI10.1002/rsa.1013zbMath0996.05106MaRDI QIDQ2746213

Van H. Vu, Michael Krivelevich, Nicholas C. Wormald, Benjamin Sudakov

Publication date: 6 November 2002

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.1013

zbMATH Keywords

eigenvalue; connectivity; random regular graphs; chromatic number; Hamiltonicity; independent set size

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60C05: Combinatorial probability

Related Items

Concentration of non‐Lipschitz functions and applications, Small subgraphs of random regular graphs, Large sets in finite fields are sumsets, On the chromatic number of random \(d\)-regular graphs, Random regular graphs of non-constant degree: concentration of the chromatic number, Sandwiching random graphs: universality between random graph models, Regular induced subgraphs of a random Graph, Hamilton cycles in 3-out, Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Automorphisms of random graphs with specified vertices
• On the independence number of random graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• The asymptotic connectivity of labelled regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The eigenvalues of random symmetric matrices
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• On the independence and chromatic numbers of random regular graphs
• Coloring graphs with sparse neighborhoods
• Asymptotic enumeration by degree sequence of graphs of high degree
• Choosability in random hypergraphs
• List coloring of random and pseudo-random graphs
• A note on Hamiltonian circuits
• Uniform generation of random regular graphs of moderate degree
• Almost all cubic graphs are Hamiltonian
• Cliques in random graphs
• Almost all regular graphs are hamiltonian
• The Choice Number of Dense Random Graphs
• The chromatic number of random graphs
• The chromatic number of random graphs