Decompositions of regular bipartite graphs

Michael S. Jacobson, Miroslaw Truszczyński, Zsolt Tuza

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


In this paper we discuss isomorphic decompositions of regular bipartite graphs into trees and forests. We prove that: (1) there is a wide class of r-regular bipartite graphs that are decomposable into any tree of size r, (2) every r-regular bipartite graph decomposes into any double star of size r, and (3) every 4-regular bipartite graph decomposes into paths P4.

Original languageEnglish
Pages (from-to)17-27
Number of pages11
JournalDiscrete Mathematics
Issue number1
StatePublished - May 3 1991

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Decompositions of regular bipartite graphs'. Together they form a unique fingerprint.

Cite this