On Induced Paths, Holes and Trees in Random Graphs

DOI10.1137/1.9781611975062.15zbMath1433.05279OpenAlexW2782449531MaRDI QIDQ5195116

Kunal Dutta, C. R. Subramanian

Publication date: 18 September 2019

Published in: 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975062.15

zbMATH Keywords

largest induced cyclelargest induced pathlargest induced tree in a dense random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Distance in graphs (05C12) Density (toughness, etc.) (05C42)

Related Items (7)

Short proofs for long induced paths ⋮ On the sizes of large subgraphs of the binomial random graph ⋮ The largest hole in sparse random graphs ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Maximum sparse induced subgraphs of the binomial random graph with given number of edges ⋮ Maximum induced forests in random graphs ⋮ Large Induced Matchings in Random Graphs

This page was built for publication: On Induced Paths, Holes and Trees in Random Graphs