Ben Barber, Daniela K\u00fchn, Allan Lo and Deryk Osthus, Advances in Mathematics, Volume 288, 22 January 2016, Pages 337\u2013385<\/a>\u00a0PDF<\/a><\/p>\n

When can the edge set of a graph 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<\/em>. Triangle divisibility is not a sufficient condition for triangle decomposition (consider ), but it is sufficient if is complete. So we would like to know how far from complete can be and triangle divisibility still remain sufficient for triangle decomposition. Nash-Williams conjectured that minimum degree (where is the number of vertices of ) should suffice for large . In this paper we prove that every triangle divisible graph with minimum degree has a triangle decomposition. We also prove similar results with any graph in place of triangles.<\/p>\n

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 we can find a graph such that and 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.<\/p>\n","protected":false},"excerpt":{"rendered":"

Ben Barber, Daniela K\u00fchn, Allan Lo and Deryk Osthus, Advances in Mathematics, Volume 288, 22 January 2016, Pages 337\u2013385\u00a0PDF When can the edge set of a graph 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 … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[3],"tags":[10,17],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/111"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=111"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/111\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=111"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=111"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=111"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}