Back to search

University of Birmingham

Path and cycle decompositions of graphs and digraphs

Abstract

dc:description.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.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Granet, Bertille

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Granet, Bertille. Path and cycle decompositions of graphs and digraphs. d_ph thesis, University of Birmingham, 2022.