# On the decomposition threshold of a given graph

Research output: Contribution to journal › Article › peer-review

## Standard

**On the decomposition threshold of a given graph.** / Glock, Stefan; Kühn, Daniela; Lo, Allan; Montgomery, Richard; Osthus, Deryk.

Research output: Contribution to journal › Article › peer-review

## Harvard

*Journal of Combinatorial Theory. Series B*, vol. 139, pp. 47-127. https://doi.org/10.1016/j.jctb.2019.02.010

## APA

*Journal of Combinatorial Theory. Series B*,

*139*, 47-127. https://doi.org/10.1016/j.jctb.2019.02.010

## Vancouver

## Author

## Bibtex

}

## RIS

TY - JOUR

T1 - On the decomposition threshold of a given graph

AU - Glock, Stefan

AU - Kühn, Daniela

AU - Lo, Allan

AU - Montgomery, Richard

AU - Osthus, Deryk

PY - 2019/11

Y1 - 2019/11

N2 - 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 fractionalversion 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.

AB - 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 fractionalversion 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.

KW - Designs

KW - Fractional graph decompositions

KW - Graph decompositions

KW - Minimum degree

UR - http://www.scopus.com/inward/record.url?scp=85063443333&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2019.02.010

DO - 10.1016/j.jctb.2019.02.010

M3 - Article

VL - 139

SP - 47

EP - 127

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -