Premium
Edge‐decomposing graphs into coprime forests
Author(s) -
Klimošová Tereza,
Thomassé Stéphan
Publication year - 2021
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.22638
Subject(s) - mathematics , combinatorics , coprime integers , conjecture , degree (music) , partition (number theory) , counterexample , graph , discrete mathematics , constant (computer programming) , computer science , physics , acoustics , programming language
The Barát‐Thomassen conjecture, recently proved in Bensmail et al. (2017), asserts that for every tree T , there is a constant c T such that every c T ‐edge‐connected graph G with number of edges (size) divisible by the size of T admits an edge partition into copies of T (a T ‐decomposition). In this paper, we investigate in which case the connectivity requirement can be dropped to a minimum degree condition. For instance, it was shown in Bensmail et al. (2019) that when T is a path with k edges, there is a constant d k such that every 24‐edge‐connected graph G with size divisible by k and minimum degree d k has a T ‐decomposition. We show in this paper that when F is a coprime forest (the sizes of its components being a coprime set of integers), any graph G with sufficiently large minimum degree has an F ‐decomposition provided that the size of F divides the size of G (no connectivity is required). A natural conjecture asked in Bensmail et al. (2019) asserts that for a fixed tree T , any graph G of size divisible by the size of T with sufficiently high minimum degree has a T ‐decomposition, provided that G is sufficiently highly connected in terms of the maximal degree of T . The case of maximum degree 2 is answered by paths. We provide a counterexample to this conjecture in the case of maximum degree 3.