Abstract
dc:description.abstractGiven graphs \(F\) and \(G\), a resolvable \(F\)-decomposition of \(G\) is a partition of its edges into \(F\)-factors. We study the existence of resolvable cycle and clique decompositions in graphs with high minimum degree and pseudo-random graphs. We show a Dirac-type result for the uniform case of the Oberwolfach problem and make progress towards a conjecture by Glock, Joos, Kim, Kühn and Osthus. Specifically, we prove that for any α>0 there is an integer r0 such that for any r\geq r0, any sufficiently large graph \(G\) on \(n\) vertices, with \(r\mid n\), even degree, and minimum degree (1/2+α)n, has a resolvable Cr-decomposition. The term \(1/2\) in the minimum degree bound is best possible. We show that any sufficiently large pseudo-random graph that satisfies the necessary divisibility conditions has a resolvable Kr-decomposition. We also prove the analogue for multipartite graphs. That is, any sufficiently large \(r\)-partite pseudo-random graph that satisfies the necessary divisibility conditions has a resolvable Kr-decomposition. Our methods are purely combinatorial and combine iterative absorption with a new technique on finding a fractional decomposition in an extended graph. Finally, we discuss the consequences of our results and some potential applications of the methods into other resolvable decomposition problems.
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
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Oviedo Timoneda, Pablo
Subjects
dc:subject × 1Rights
- Language dc:language.dcterms_iso639_2
- eng