Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T18:45:20.413Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 K3-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
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 6 , November 2017 , pp. 911 - 943
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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