arXiv Analytics

Sign in

arXiv:0809.2879 [math.CO]AbstractReferencesReviewsResources

An analogue of the Szemeredi Regularity Lemma for bounded degree graphs

Gábor Elek, Gábor Lippner

Published 2008-09-17, updated 2009-04-18Version 2

We show that a sufficiently large graph of bounded degree can be decomposed into quasi-homogeneous pieces. The result can be viewed as a "finitarization" of the classical Farrell-Varadarajan Ergodic Decomposition Theorem.

Comments: Corrected an error in the proof of the Homogeneity Lemma. A new result is proved about edge-colorings of convergent graph sequences
Categories: math.CO, math.DS
Subjects: 05C99, 37A20
Related articles: Most relevant | Search more
arXiv:0711.2800 [math.CO] (Published 2007-11-18, updated 2009-07-02)
Parameter testing with bounded degree graphs of subexponential growth
arXiv:2003.05637 [math.CO] (Published 2020-03-12)
Conflict-free coloring on closed neighborhoods of bounded degree graphs
arXiv:1407.5075 [math.CO] (Published 2014-07-18)
Separation dimension of bounded degree graphs

Links

Toolbox