On Induced Paths, Holes, and Trees in Random Graphs

DOI10.1137/21M1409895OpenAlexW4319071296MaRDI QIDQ5883287

Kunal Dutta, C. R. Subramanian

Publication date: 30 March 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

pathscyclesrandom graphsinduced subgraphstrees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38)

Related Items (1)

MIP formulations for induced graph optimization problems: a tutorial

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trees in random graphs
• Induced trees in sparse random graphs
• On the order of the largest induced tree in a random graph
• 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
• Nearly perfect matchings in regular simple hypergraphs
• Large induced trees in sparse random graphs
• Concentration of non‐Lipschitz functions and applications
• On the probability of independent sets in random graphs
• On the Method of Typical Bounded Differences
• The chromatic number of random graphs
• Concentration of multivariate polynomials and its applications
• The largest hole in sparse random graphs

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