Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs

DOI10.1016/J.DISC.2008.11.023zbMath1229.05089OpenAlexW1975473448MaRDI QIDQ1045170

Joanna Polcyn, Andrzej Ruciński

Publication date: 15 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2008.11.023

zbMATH Keywords

diameteredge decomposition\(\varepsilon \)-regular graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Vertex degrees (05C07)

Related Items (1)

Decompositions into Subgraphs of Small Diameter

Cites Work

• Unnamed Item
• Unnamed Item
• Large holes in quasi-random graphs
• Low diameter graph decompositions
• Perfect matchings in \(\varepsilon\)-regular graphs
• Matrix-free proof of a regularity characterization
• On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Strong edge colorings of uniform graphs
• Short paths in quasi-random triple systems with sparse underlying graphs
• The Algorithmic Aspects of the Regularity Lemma
• Regular pairs in sparse random graphs I
• An Optimal Algorithm for Checking Regularity
• Short paths in 3-uniform quasi-random hypergraphs
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph

This page was built for publication: Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs