Projects per year
Abstract
The topic of this PhD thesis is graph decompositions. While there exist various kinds of decompositions, this thesis focuses on three problems concerning edgedecompositions. Given a family of graphs H we ask the following question: When can the edgeset of a graph be partitioned so that each part induces a subgraph isomorphic to a member of H? Such a decomposition is called an Hdecomposition. Apart from the existence of an Hdecomposition, we are also interested in the number of parts needed in an Hdecomposition.
Firstly, we show that for every tree T there exists a constant k(T) such that every k(T)edgeconnected graph whose size is divisible by the size of T admits a Tdecomposition. This proves a conjecture by Barát and Thomassen from 2006.
Moreover, we introduce a new arboricity notion where we restrict the diameter of the trees in a decomposition into forests. We conjecture that for every natural number k there exists a natural number d(k) such that the following holds: If G can be decomposed into k forests, then G can be decomposed into k + 1 forests in which each tree has diameter at most d(k). We verify this conjecture for
k ≤ 3. As an application we show that every 6edgeconnected planar graph contains two edgedisjoint 18/19 thin spanning trees.
Finally, we make progress on a conjecture by Baudon, Bensmail, Przybyło, and Wozniak stating that if a graph can be decomposed into locally irregular graphs, then there exists such a decomposition with at most 3 parts. We show that this conjecture is true if the number 3 is replaced by 328, establishing the first constant upper bound for this problem.
Firstly, we show that for every tree T there exists a constant k(T) such that every k(T)edgeconnected graph whose size is divisible by the size of T admits a Tdecomposition. This proves a conjecture by Barát and Thomassen from 2006.
Moreover, we introduce a new arboricity notion where we restrict the diameter of the trees in a decomposition into forests. We conjecture that for every natural number k there exists a natural number d(k) such that the following holds: If G can be decomposed into k forests, then G can be decomposed into k + 1 forests in which each tree has diameter at most d(k). We verify this conjecture for
k ≤ 3. As an application we show that every 6edgeconnected planar graph contains two edgedisjoint 18/19 thin spanning trees.
Finally, we make progress on a conjecture by Baudon, Bensmail, Przybyło, and Wozniak stating that if a graph can be decomposed into locally irregular graphs, then there exists such a decomposition with at most 3 parts. We show that this conjecture is true if the number 3 is replaced by 328, establishing the first constant upper bound for this problem.
Original language  English 

Place of Publication  Kgs. Lyngby 

Publisher  Technical University of Denmark 
Number of pages  97 
Publication status  Published  2016 
Series  DTU Compute PHD2016 

Number  431 
ISSN  09093192 
Fingerprint Dive into the research topics of 'Graph Decompositions'. Together they form a unique fingerprint.
Projects
 1 Finished

Decomposition of Graphs
Merker, M., Thomassen, C., Gørtz, I. L., Barat, J. & BangJensen, J.
01/09/2013 → 23/11/2016
Project: PhD