Short proofs for long induced paths

DOI10.1017/S0963548322000013MaRDI QIDQ5886345zbMATH OpenOpenAlexWikidataFDO

Authors Nemanja Draganić, Stefan Glock, Michael Krivelevich

Publication date 31 March 2023

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

random graphsDFSinduced pathssupercriticalsize-Ramsey numbers

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Recommendations

• On large induced trees and long induced paths in sparse random graphs
• On induced paths, holes and trees in random graphs
• On Induced Paths, Holes, and Trees in Random Graphs
• Long induced paths in graphs
• Longest paths in random hypergraphs

Cites work

• scientific article; zbMATH DE number 4029619 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3999982 (Why is no real title available?)
• scientific article; zbMATH DE number 932179 (Why is no real title available?)
• An alternative proof of the linearity of the size-Ramsey number of paths
• Expanders -- how to find them, and what to find in them
• Induced trees in sparse random graphs
• Introduction to Random Graphs
• Large holes in sparse random graphs
• Large induced trees in sparse random graphs
• Long cycles in locally expanding graphs, with applications
• Maximal induces trees in sparse random graphs
• New lower bounds on the size-Ramsey number of a path
• On induced paths, holes and trees in random graphs
• On large induced trees and long induced paths in sparse random graphs
• On size Ramsey number of paths, trees, and circuits. I
• On some multicolor Ramsey properties of random graphs
• Path Ramsey number for random graphs
• Random graphs.
• The Induced Size-Ramsey Number of Cycles
• The largest hole in sparse random graphs
• The phase transition in random graphs: a simple proof
• The size Ramsey number
• The size of the largest hole in a random graph
• Trees in random graphs

Cited in

(8)

• Estimating the number of graphs containing very long induced paths
• Effective bounds for induced size-Ramsey numbers of cycles (extended abstract)
• Long induced paths in expanders
• Sparse graphs without long induced paths
• Induced Ramsey problems for trees and graphs with bounded treewidth
• The emergence of a giant rainbow component
• Longest paths in random hypergraphs
• scientific article; zbMATH DE number 2119679 (Why is no real title available?)

This page was built for publication: Short proofs for long induced paths

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