The largest hole in sparse random graphs

DOI10.1002/rsa.21078zbMath1522.05422arXiv2106.00597OpenAlexW4214536382MaRDI QIDQ6052472

Stefan Glock, Michael Krivelevich, Nemanja Draganić

Publication date: 17 October 2023

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

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

zbMATH Keywords

holerandom graphinduced path

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Related Items (2)

On Induced Paths, Holes, and Trees in Random Graphs ⋮ Short proofs for long induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The size Ramsey number of a directed path
• Trees in random graphs
• On the independence number of random graphs
• Induced trees in sparse random graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Large holes in sparse random graphs
• Maximal induces trees in sparse random graphs
• On large induced trees and long induced paths in sparse random graphs
• The size of the largest hole in a random graph
• Random minimum length spanning trees in regular graphs
• Large induced trees in sparse random graphs
• Local algorithms for independent sets are half-optimal
• The phase transition in random graphs: A simple proof
• Independent Sets in Random Graphs from the Weighted Second Moment Method
• On independent sets in random graphs
• On colouring random graphs
• Cliques in random graphs
• On Induced Paths, Holes and Trees in Random Graphs
• Large Induced Matchings in Random Graphs
• The chromatic number of random graphs
• Limits of local algorithms over sparse random graphs

This page was built for publication: The largest hole in sparse random graphs