Date
Tue, 30 May 2023
Time
14:00 - 15:00
Location
L5
Speaker
Allan Lo
Organisation
University of Birmingham

Magnant and Martin conjectured that every $d$-regular graph on $n$ vertices can be covered by $n/(d+1)$ vertex-disjoint paths. Gruslys and Letzter verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all $\alpha>0$, there exists $n_0=n_0(\alpha)$ such that every $d$-regular digraph on $n$ vertices with $d \ge \alpha n $ can be covered by at most $n/(d+1)$ vertex-disjoint cycles. Moreover if $G$ is an oriented graph, then $n/(2d+1)$ cycles suffice. This also establishes Jackson's long standing conjecture for large $n$ that every $d$-regular oriented graph on $n$ vertices with $n\leq 4d+1$ is Hamiltonian.
This is joint work with Viresh Patel and  Mehmet Akif Yıldız.

Please contact us with feedback and comments about this page. Last updated on 09 May 2023 10:09.