Martin Merker: Graphs are mathematical structures which are often used to model networks arising in different areas. In particular algorithms on graphs play an important role not only in theoretical computer science but also in various other fields such as optimization, neuroscience or social networks.
The topic of this PhD project is graph decompositions which, broadly speaking, involves partitioning a graph into parts of a certain structure. It is a natural theoretical question whether this is possible, but the topic is also important from an algorithmic point of view: Knowing in which way a graph is composed of smaller subgraphs might improve the running time of an algorithm significantly. While there exist various kinds of decompositions that have been studied, this project focuses on several problems concerning edge-decompositions.
We investigate when the edge-set of a graph can be partitioned so that each part induces a certain subgraph. Many graph-theoretic problems can be phrased in terms of edge-decompositions. To give one example, the edge-chromatic number of a graph is the same as the smallest number of matchings needed to decompose the graph.
The following question plays a central role in the project: When can a graph be decomposed into copies of a given tree? Barát and Thomassen conjectured ten years ago that large edge-connectivity is a sufficient condition, provided the size of the graph is divisible by the size of the tree. As part of the PhD project, this conjecture has been proved.
Effective start/end date 01/09/2013 → 23/11/2016
Published as PhD report: Graph Decompositions
Supervisor: Carsten Thomassen
Section for Algorithms, Logic and Graphs