Covering cycles in sparse graphs

DOI10.1002/rsa.21045zbMath1522.05258arXiv2003.03311OpenAlexW3203920671MaRDI QIDQ6074700

Miloš Trujić, Nemanja Škorić, Frank Mousset

Publication date: 12 October 2023

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

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

zbMATH Keywords

random graphsabsorbing methodresiliencepseudo-random graphscovering cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Small subsets inherit sparse \(\varepsilon\)-regularity
• Proof of the bandwidth conjecture of Bollobás and Komlós
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• Vertex coverings by monochromatic cycles and trees
• Proof of the Seymour conjecture for large graphs
• A condition for matchability in hypergraphs
• Decompositions into isomorphic rainbow spanning trees
• Spanning trees in random graphs
• Hamiltonicity in random graphs is born resilient
• Robust Hamiltonicity of random directed graphs
• Stability for vertex cycle covers
• Covering cycles and \(k\)-term degree sums
• Corrádi and Hajnal's Theorem for Sparse Random Graphs
• Long cycles in subgraphs of (pseudo)random directed graphs
• Szemerédi's Regularity Lemma for Matrices and Sparse Graphs
• Local resilience of almost spanning trees in random graphs
• Dirac's theorem for random graphs
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Almost all Steiner triple systems have perfect matchings
• Local resilience of graphs
• Triangle Factors in Random Graphs
• Combinatorial theorems relative to a random set
• Local resilience of an almost spanning k‐cycle in random graphs
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• Hamiltonicity in random directed graphs is born resilient
• The Bandwidth Theorem in sparse graphs
• On Komlós’ tiling theorem in random graphs
• Resilience of perfect matchings and Hamiltonicity in random graph processes
• Large-scale structures in random graphs
• Robustness of graph properties
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• Some Theorems on Abstract Graphs

This page was built for publication: Covering cycles in sparse graphs