<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T10:08:34Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/17138" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/17138</identifier><datestamp>2025-03-26T23:35:03Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Postle, Luke</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="1cdad58d-db48-4ff6-9978-657ff504fbb6" confidence="600">Moore, Benjamin</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2021-07-09T12:51:47Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2021-07-09T12:51:47Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2021-07-09</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2021-07-05</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/17138</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The focus of this thesis is to take theorems which deal with ``integral&amp;quot; objects in graph theory and consider fractional refinements of them to gain additional structure. &#xd;
&#xd;
A classic theorem of Hakimi says that for an integer $k$, a graph has maximum average degree at most $2k$ if and only if the graph decomposes into $k$ pseudoforests. To find a fractional refinement of this theorem, one simply needs to consider the instances where the maximum average degree is fractional. &#xd;
&#xd;
 We prove that for any positive integers $k$ and $d$, if $G$ has maximum average degree at most $2k + \frac{2d}{k+d+1}$, then $G$ decomposes into $k+1$ pseudoforests, where one of pseudoforests has every connected component containing at most $d$ edges, and further this pseudoforest is acyclic. The maximum average degree bound is best possible for every choice of $k$ and $d$. &#xd;
&#xd;
Similar to Hakimi&amp;apos;s Theorem, a classical theorem of Nash-Williams says that a graph has fractional arborcity at most $k$ if and only if $G$ decomposes into $k$ forests. The Nine Dragon Tree Theorem, proven by Jiang and Yang, provides a fractional refinement of Nash-Williams Theorem. It says, for any positive integers $k$ and $d$, if a graph $G$ has fractional arboricity at most $k + \frac{d}{k+d+1}$, then $G$ decomposes into $k+1$ forests, where one of the forests has maximum degree $d$. &#xd;
&#xd;
We prove a strengthening of the Nine Dragon Tree Theorem in certain cases. Let $k=1$ and $d \in \{3,4\}$. Every graph with fractional arboricity at most $1 + \frac{d}{d+2}$ decomposes into two forests $T$ and $F$ where $F$ has maximum degree $d$, every component of $F$ contains at most one vertex of degree $d$, and if $d= 4$, then every component of $F$ contains at most $8$ edges $e=xy$ such that both $\deg(x) \geq 3$ and $\deg(y) \geq 3$.&#xd;
&#xd;
In fact, when $k = 1$ and $d=3$, we prove that every graph with fractional arboricity $1 + \frac{3}{5}$ decomposes into two forests $T,F$ such that $F$ has maximum degree $3$, every component of $F$ has at most one vertex of degree $3$, further if a component of $F$ has a vertex of degree $3$ then it has at most $14$ edges, and otherwise a component of $F$ has at most $13$ edges.&#xd;
&#xd;
&#xd;
Shifting focus to problems which partition the vertex set, circular colouring provides a way to fractionally refine colouring problems. A classic theorem of Tuza says that every graph with no cycles of length $1 \bmod k$ is $k$-colourable. Generalizing this to circular colouring, we get the following: &#xd;
&#xd;
Let $k$ and $d$ be relatively prime, with $k&amp;gt;2d$, and let $s$ be the element of $\mathbb{Z}_k$ such that $sd \equiv 1\mod k$.  Let $xy$ be an edge in a graph $G$. If $G-xy$ is $(k,d)$-circular-colorable and $G$ is not, then $xy$ lies in at least one&#xd;
cycle in $G$ of length congruent to $is \mod k$ for some $i$ in&#xd;
$\{1,\ldots,d\}$.  If this does not occur with $i \in\{1,\ldots,d-1\}$, then $xy$ lies in at least two cycles of length $1 \mod k$ and $G-xy$ contains a cycle of length $0 \mod k$.&#xd;
&#xd;
This theorem is best possible with regards to the number of congruence classes when $k = 2d+1$.&#xd;
&#xd;
A classic theorem of Gr\&amp;quot;{o}tzsch says that triangle free planar graphs are $3$-colourable. There are many generalizations of this result, however fitting the theme of fractional refinements, Jaeger conjectured that every planar graph of girth $4k$ admits a homomorphism to $C_{2k+1}$. While we make no progress on this conjecture directly, one way to approach the conjecture is to prove critical graphs have large average degree.  On this front, we prove:&#xd;
&#xd;
Every $4$-critical graph which does not have a $(7,2)$-colouring and is not $K_{4}$ or $W_{5}$ satisfies $e(G) \geq \frac{17v(G)}{10}$, and &#xd;
every triangle free $4$-critical graph satisfies $e(G) \geq \frac{5v(G)+2}{3}$. &#xd;
&#xd;
In the case of the second theorem, a result of Davies shows there exists infinitely many triangle free $4$-critical graphs satisfying $e(G) = \frac{5v(G) +4}{3}$, and hence the second theorem is close to being tight. It also generalizes results of Thomas and Walls, and also Thomassen, that girth $5$ graphs embeddable on the torus, projective plane, or Klein bottle are $3$-colourable. &#xd;
&#xd;
Lastly, a theorem of Cereceda, Johnson, and van den Heuvel, says that given a $2$-connected bipartite planar graph $G$ with no separating four-cycles and a $3$-colouring $f$, then one can obtain all $3$-colourings from $f$ by changing one vertices&amp;apos; colour at a time if and only if $G$ has at most one face of size $6$. &#xd;
&#xd;
We give the natural generalization of this to circular colourings when $\frac{p}{q} &amp;lt; 4$.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Strong Nine Dragon Tree Conjecture</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Homomorphisms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Potential Method</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Graph Decompositions</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Fractional refinements of integral theorems</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Postle, Luke</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>