Partitioning into graphs with only small components

Noga Alon, Guoli Ding, Bogdan Oporowski, Dirk Vertigan

Research output: Contribution to journalArticlepeer-review

73 Scopus citations

Abstract

The paper presents several results on edge partitions and vertex partitions of graphs into graphs with bounded size components. We show that every graph of bounded tree-width and bounded maximum degree admits such partitions. We also show that an arbitrary graph of maximum degree four has a vertex partition into two graphs, each of which has components on at most 57 vertices. Some generalizations of the last result are also discussed.

Original languageEnglish (US)
Pages (from-to)231-243
Number of pages13
JournalJournal of Combinatorial Theory. Series B
Volume87
Issue number2
DOIs
StatePublished - Mar 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Edge partitions
  • Small components
  • Tree-width
  • Vertex partitions

Fingerprint

Dive into the research topics of 'Partitioning into graphs with only small components'. Together they form a unique fingerprint.

Cite this