Fractional Clique Decompositions of Dense Partite Graphs

2016/03/03 by Montgomery, Richard · 2 citations
#05C70 #05C72 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1603.01039

Abstract

We give a minimum degree condition sufficent to ensure the existence of a fractional K_r-decomposition in a balanced r-partite graph (subject to some further simple necessary conditions). This generalises the non-partite problem studied recently by Barber, Lo, Kühn, Osthus and the author, and the 3-partite fractional K₃-decomposition problem studied recently by 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) K_r-decomposition in a balanced r-partite graph (subject to the same simple necessary conditions).

Cited by

• On fractional triangle decompositions of random graphs
• Beyond Nash-Williams: Counterexamples to Clique Decomposition Thresholds for All Cliques Larger than Triangles

Related

• Clique decompositions of multipartite graphs and completion of Latin squares
• Fractional clique decompositions of dense graphs
• Fractional triangle decompositions of dense 3-partite graphs
• Fractional Clique Decompositions of Dense Hypergraphs
• Fractional triangle decompositions in graphs with large minimum degree