On the decomposition threshold of a given graph

Research output: Contribution to journalArticlepeer-review

Standard

Harvard

APA

Vancouver

Author

Bibtex

@article{0a4d0f5ac47f4ccf824013c287f34fc2,
title = "On the decomposition threshold of a given graph",
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 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 {\textquoteleft}iterative{\textquoteright} absorbing approach.",
keywords = "Designs, Fractional graph decompositions, Graph decompositions, Minimum degree",
author = "Stefan Glock and Daniela K{\"u}hn and Allan Lo and Richard Montgomery and Deryk Osthus",
year = "2019",
month = nov,
doi = "10.1016/j.jctb.2019.02.010",
language = "English",
volume = "139",
pages = "47--127",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Elsevier",

}

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 -