Premium
On the exact decomposition threshold for even cycles
Author(s) -
Taylor Amelia
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22399
Subject(s) - mathematics , divisibility rule , bipartite graph , combinatorics , decomposition , graph , set (abstract data type) , degree (music) , enhanced data rates for gsm evolution , discrete mathematics , computer science , ecology , physics , acoustics , biology , programming language , telecommunications
A graph G has a C k ‐decomposition if its edge set can be partitioned into cycles of length k . We show that if δ ( G ) ≥ 2 ∣ G ∣ ∕ 3 − 1 , then G has a C 4 ‐decomposition, and if δ ( G ) ≥ ∣ G ∣ ∕ 2 , then G has a C 2 k ‐decomposition, where k ∈ N and k ≥ 4 (we assume G is large and satisfies necessary divisibility conditions). These minimum degree bounds are best possible and provide exact versions of asymptotic results obtained by Barber, Kühn, Lo and Osthus. In the process, we obtain asymptotic versions of these results when G is bipartite or satisfies certain expansion properties.