# On the decomposition threshold of a given graph

Research output: Contribution to journal › Article

## Authors

## 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.

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 language | English |
---|---|

Pages (from-to) | 47-127 |

Number of pages | 81 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 139 |

Early online date | 29 Mar 2019 |

Publication status | Published - Nov 2019 |

## Keywords

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