Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T05:19:17.386Z Has data issue: false hasContentIssue false
  • English
  • Français

Fractional Clique Decompositions of Dense Partite Graphs

Part of: Graph theory

Published online by Cambridge University Press:  19 June 2017

RICHARD MONTGOMERY
RICHARD MONTGOMERY*
Affiliation:
Trinity College, Cambridge CB2 1TQ, UK (e-mail: rhm34@cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We give a minimum degree condition sufficient to ensure the existence of a fractional Kr -decomposition in a balanced r-partite graph (subject to some further simple necessary conditions). This generalizes the non-partite problem studied recently by Barber, Lo, Kühn, Osthus and the author, and the 3-partite fractional K 3-decomposition problem studied recently by Bowditch and Dukes. Combining our result with recent work by Barber, Kühn, Lo, Osthus and Taylor, this gives a minimum degree condition sufficient to ensure the existence of a (non-fractional) Kr -decomposition in a balanced r-partite graph (subject to the same simple necessary conditions).

MSC classification

Primary: 05C51: Graph designs and isomomorphic decomposition
Secondary: 05C72: Fractional graph theory, fuzzy graph theory

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 6 , November 2017 , pp. 911 - 943
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Barber, B., Kühn, D., Lo, A. and Osthus, D. (2016) Edge-decompositions of graphs with high minimum degree. Adv. Math. 288 337–385.Google Scholar
[2] Barber, B., Kühn, D., Lo, A., Montgomery, R. and Osthus, D. (2017) Fractional clique decompositions of dense graphs and hypergraphs. J. Combinatorial Theory Series B, to appear.Google Scholar
[3] Barber, B., Kühn, D., Lo, A., Osthus, D. and Taylor, A. (2017) Clique decompositions of multipartite graphs and completion of Latin squares. J. Combinatorial Theory Series A 151 146–201.CrossRefGoogle Scholar
[4] Bowditch, F. and Dukes, P. (2015) Fractional triangle decompositions of dense 3-partite graphs. arXiv:1510.08998 Google Scholar
[5] Dross, F. (2016) Fractional triangle decompositions in graphs with large minimum degree. SIAM J. Discrete Math. 30 36–42.CrossRefGoogle Scholar
[6] Dukes, P. (2012) Rational decomposition of dense hypergraphs and some related eigenvalue estimates. Linear Algebra Appl. 436 3736–3746.CrossRefGoogle Scholar
[7] Dukes, P. (2015) Corrigendum to ‘Rational decomposition of dense hypergraphs and some related eigenvalue estimates (Linear Algebra Appl. 436 (2012) 3736–3746)’. Linear Algebra Appl. 467 267–269.Google Scholar
[8] Garaschuk, K. (2014) Linear methods for rational triangle decompositions. PhD thesis, University of Victoria.Google Scholar
[9] Haxell, P. and Rödl, V. (2001) Integer and fractional packings in dense graphs. Combinatorica 21 13–38.Google Scholar
[10] Keevash, P. (2014) The existence of designs. arXiv:1401.3665 Google Scholar
[11] Kirkman, T. (1847) On a problem in combinations. The Cambridge and Dublin Mathematical Journal II 191–204.Google Scholar
[12] Wilson, R. (1975) Decomposition of complete graphs into subgraphs isomorphic to a given graph. Congress. Numer. XV 647–659.Google Scholar
[13] Yuster, R. (2005) Asymptotically optimal Kk -packings of dense graphs via fractional Kk -decompositions. J. Combin. Theory Ser. B 95 1–11.Google Scholar