Edge-decompositions of graphs with high minimum degree

Ben Barber, Daniela Kühn, Allan Lo and Deryk Osthus, Advances in Mathematics, Volume 288, 22 January 2016, Pages 337–385 PDF

When can the edge set of a graph G be partitioned into triangles? Two obvious necessary conditions are that the total number of edges is divisible by 3 and the degree of every vertex is even. We call these conditions triangle divisibility. Triangle divisibility is not a sufficient condition for triangle decomposition (consider C_6), but it is sufficient if G is complete. So we would like to know how far from complete G can be and triangle divisibility still remain sufficient for triangle decomposition. Nash-Williams conjectured that minimum degree 3n/4 (where n is the number of vertices of G) should suffice for large n. In this paper we prove that every triangle divisible graph with minimum degree 9n/10 + o(n) has a triangle decomposition. We also prove similar results with any graph F in place of triangles.

The proof uses the absorbing method. It is very easy to remove triangles at the beginning of the process, but very hard at the end. So we make use of the flexibility we have at the beginning to make a plan for dealing with a small remainder. The key idea is that given a possible remainder R we can find a graph A such that A and A \cup R both have triangle decompositions. By reserving sufficiently many such A at the start of the process we know that we will be able to solve our problems at the end.

Leave a Reply

Your e-mail address will not be published.