Clique decompositions of multipartite graphs and completion of latin squares

Ben Barber, Daniela Kühn, Allan Lo, Deryk Osthus, Amelia Taylor

Research output: Contribution to journalArticle (Academic Journal)peer-review

10 Citations (Scopus)
243 Downloads (Pure)

Abstract

Our main result essentially reduces the problem of finding an edge-decomposition of a balanced r-partite graph of large minimum degree into r-cliques to the problem of finding a fractional r-clique decomposition or an approximate one. Together with very recent results of Dukes as well as Montgomery on fractional decompositions into triangles and cliques respectively, this gives the best known bounds on the minimum degree which ensures an edge-decomposition of an r-partite graph into r-cliques (subject to trivially necessary divisibility conditions). The 3-partite case significantly improves existing bounds, the case r ≥ 4 extends a result of Chowla, Erdős and Straus on the existence of r-clique decompositions of complete r-partite graphs to non-complete r-partite graphs. The case of triangles translates into the setting of partially completed Latin squares and more generally the case of r-cliques translates into the setting of partially completed mutually orthogonal Latin squares.
Original languageEnglish
Pages (from-to)146-201
Number of pages56
JournalJournal of Combinatorial Theory, Series A
Volume151
Early online date10 May 2017
DOIs
Publication statusPublished - Oct 2017

Keywords

  • Edge-decompositions
  • Mutually orthogonal
  • Latin squares

Fingerprint Dive into the research topics of 'Clique decompositions of multipartite graphs and completion of latin squares'. Together they form a unique fingerprint.

Cite this