Path and cycle decompositions of graphs and digraphs

Granet, Bertille (2022). Path and cycle decompositions of graphs and digraphs. University of Birmingham. Ph.D.

Preview

Granet2022PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (1MB) | Preview

Abstract

In this thesis, we make progress on five long standing conjectures on path and cycle decompositions of graphs and digraphs. Firstly, we confirm a conjecture of Jackson from 1981 by showing that the edges of any sufficiently large regular bipartite tournament can be decomposed into Hamilton cycles. Along the way, we also prove several further results, including a conjecture of Liebenau and Pehova on Hamilton decompositions of dense bipartite digraphs.

Secondly, we determine the minimum number of paths required to decompose the edges of any sufficiently large tournament of even order, thus resolving a conjecture of Alspach, Mason, and Pullman from 1976. We also prove an asymptotically optimal result for tournaments of odd order.

Finally, we give asymptotically best possible upper bounds on the minimum number of paths, cycles, and cycles and edges required to decompose the edges of any sufficiently large dense graph. This makes progress on three famous conjectures from the 1960s: Gallai's conjecture, Hajós' conjecture, and the Erdős-Gallai conjecture, respectively.

This includes joint work with António Girão, Daniela Kühn, Allan Lo, and Deryk Osthus.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):