Can a graph have distinct regular partitions?

Noga Alon, Asaf Shapira, Uri Stav

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular-partition of its vertex set. In this paper we address the following problem: can a graph have two "distinct" regular partitions? It turns out that (as observed by several researchers) for the standard notion of a regular partition, one can construct a graph that has very distinct regular partitions. On the other hand we show that for the stronger notion of a regular partition that has been recently studied, all such regular partitions of the same graph must be very "similar". En route, we also give a short argument for deriving a recent variant of the regularity lemma obtained independently by Rödl and Schacht ([11]) and Lovász and Szegedy ([9],[10]), from a previously known variant of the regularity lemma due to Alon et al. [2]. The proof also provides a deterministic polynomial time algorithm for finding such partitions.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783540735441
StatePublished - 2007
Externally publishedYes
Event13th Annual International Computing and Combinatorics Conference, COCOON 2007 - Banff, Canada
Duration: Jul 16 2007Jul 19 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4598 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th Annual International Computing and Combinatorics Conference, COCOON 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Can a graph have distinct regular partitions?'. Together they form a unique fingerprint.

Cite this