Short paths in -regular pairs and small diameter decompositions of dense graphs

DOI10.1016/J.DISC.2008.11.023MaRDI QIDQ1045170zbMATH OpenOpenAlexFDO

Authors 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

\(\varepsilon \)-regular graphsdiameteredge decomposition

Mathematics Subject Classification ID

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

Recommendations

• Decompositions into subgraphs of small diameter
• Holes in graphs
• On vertex-disjoint paths in regular graphs
• Regular pairs in sparse random graphs I
• Decomposing large graphs with small graphs of high density

Cites work

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

Cited in

(2)

• scientific article; zbMATH DE number 867634 (Why is no real title available?)
• Decompositions into subgraphs of small diameter

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1045170)