Back to search

University of Birmingham

On resolvable decomposition problems

Abstract

dc:description.abstract

Given 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 × 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

Oviedo Timoneda, Pablo. On resolvable decomposition problems. d_ph thesis, University of Birmingham, 2024.