Tuza's conjecture for random graphs

DOI10.1002/rsa.21057zbMath1522.05432arXiv2007.04351OpenAlexW3212177754WikidataQ113913008 ScholiaQ113913008MaRDI QIDQ6076736

Jeffry Kahn, Jinyoung Park

Publication date: 17 October 2023

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

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

zbMATH Keywords

branching processrandom graphcouplingTuza's conjecturerandom greedy matching

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A stability theorem on fractional covering of triangles by edges
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Near perfect coverings in graphs and hypergraphs
• Packing and covering triangles in graphs
• Matchings and covers in hypergraphs
• Probability on Trees and Networks
• Asymptotic packing via a branching process
• [https://portal.mardi4nfdi.de/wiki/Publication:4870539 A linear programming perspective on the Frankl?R�dl?Pippenger theorem]
• Large triangle packings and Tuza’s conjecture in sparse random graphs
• Upper bounds for the distance in total variation between the binomial or negative binomial and the Poisson distribution