Sparse balanced partitions and the complexity of subgraph problems

Noga Alon, Dániel Marx

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

We consider the problem of partitioning the vertices of an n-vertex graph with maximum degree d into k classes V1;⋯, Vk of size at most ⌊n/k⌋ in a way that minimizes the number of pairs (i,j) for which there is an edge between Vi and Vj. We show that there is always such a partition with O(k2-2/d) adjacent pairs, and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems.

Original languageEnglish (US)
Pages (from-to)631-644
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume25
Issue number2
DOIs
StatePublished - 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Graph partitions
  • Minors
  • Subgraph problems

Fingerprint Dive into the research topics of 'Sparse balanced partitions and the complexity of subgraph problems'. Together they form a unique fingerprint.

  • Cite this