On the decomposition threshold of a given graph

Research output: Contribution to journalArticle

Colleges, School and Institutes

Abstract

We study the F-decomposition threshold δF for a given graph F. Here an F-decomposition of a graph G is a collection of edge-disjoint copies of F in G which togetherncover every edge of G. (Such an F-decomposition can only exist if G is F-divisible, i.e. if e(F) | e(G) and each vertex degree of G can be expressed as a linear combination of the vertex degrees of F.) The F-decomposition threshold δF is the smallest value ensuring that an F-divisible graph G on n vertices with δ(G) ≥ (δF + o(1))n has an F-decomposition. Our main results imply the following for a given graph F, where δ∗F is the fractional
version of δF and χ := χ(F): (i) δF ≤ max{δ∗F , 1 − 1/(χ + 1)}; (ii) if χ ≥ 5, then δF ∈ {δ∗F , 1 − 1/χ, 1 − 1/(χ + 1)}; (iii) we determine δF if F is bipartite. In particular, (i) implies that δKr = δ∗Kr. Our proof involves further developments of the recent ‘iterative’ absorbing approach.

Details

Original languageEnglish
Pages (from-to)47-127
Number of pages81
JournalJournal of Combinatorial Theory. Series B
Volume139
Early online date29 Mar 2019
Publication statusPublished - Nov 2019

Keywords

  • Designs, Fractional graph decompositions, Graph decompositions, Minimum degree