Holes in graphs
The electronic journal of combinatorics, Tome 9 (2002)
The celebrated Regularity Lemma of Szemerédi asserts that every sufficiently large graph $G$ can be partitioned in such a way that most pairs of the partition sets span $\epsilon$-regular subgraphs. In applications, however, the graph $G$ has to be dense and the partition sets are typically very small. If only one $\epsilon$-regular pair is needed, a much bigger one can be found, even if the original graph is sparse. In this paper we show that every graph with density $d$ contains a large, relatively dense $\epsilon$-regular pair. We mainly focus on a related concept of an $(\epsilon,\sigma)$-dense pair, for which our bound is, up to a constant, best possible.
@article{10_37236_1618,
author = {Yuejian Peng and Vojtech R\"odl and Andrzej Ruci\'nski},
title = {Holes in graphs},
journal = {The electronic journal of combinatorics},
year = {2002},
volume = {9},
doi = {10.37236/1618},
zbl = {0992.05048},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1618/}
}
Yuejian Peng; Vojtech Rödl; Andrzej Ruciński. Holes in graphs. The electronic journal of combinatorics, Tome 9 (2002). doi: 10.37236/1618
Cité par Sources :