<?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-22T22:19:34Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/14862" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/14862</identifier><datestamp>2025-03-26T23:33:17Z</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="7dea7155-d6e8-4dcd-b8fc-f5ad3d4d6007" confidence="600">Kelly, Thomas</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2019-08-09T13:14:36Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2019-08-09T13:14:36Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2019-08-09</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2019-08-07</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/14862</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Many of the most celebrated and influential results in graph coloring, such as Brooks&amp;apos; Theorem and Vizing&amp;apos;s Theorem, relate a graph&amp;apos;s chromatic number to its clique number or maximum degree.  Currently, several of the most important and enticing open problems in coloring, such as Reed&amp;apos;s $\omega, \Delta, \chi$ Conjecture, follow this theme.&#xd;
&#xd;
This thesis both broadens and deepens this classical paradigm.&#xd;
  &#xd;
In Part~1, we tackle list-coloring problems in which the number of colors available to each vertex $v$ depends on its degree, denoted $d(v)$, and the size of the largest clique containing it, denoted $\omega(v)$.  We make extensive use of the probabilistic method in this part.&#xd;
&#xd;
We conjecture the ``list-local version&amp;apos;&amp;apos; of Reed&amp;apos;s Conjecture, that is every graph is $L$-colorable if $L$ is a list-assignment such that &#xd;
$$|L(v)| \geq \lceil (1 - \varepsilon)(d(v) + 1) + \varepsilon\omega(v))\rceil$$&#xd;
for each vertex $v$ and $\varepsilon \leq 1/2$, and we prove this for $\varepsilon \leq 1/330$ under some mild additional assumptions.&#xd;
&#xd;
We also conjecture the ``$\mathrm{mad}$ version&amp;apos;&amp;apos; of Reed&amp;apos;s Conjecture, even for list-coloring.  That is, for $\varepsilon \leq 1/2$, every graph $G$ satisfies&#xd;
$$\chi_\ell(G) \leq \lceil (1 - \varepsilon)(\mad(G) + 1) + \varepsilon\omega(G)\rceil,$$&#xd;
where $\mathrm{mad}(G)$ is the maximum average degree of $G$.  We prove this conjecture for small values of $\varepsilon$, assuming $\omega(G) \leq \mathrm{mad}(G) - \log^{10}\mathrm{mad}(G)$.  We actually prove a stronger result that improves bounds on the density of critical graphs without large cliques, a long-standing problem, answering a question of Kostochka and Yancey.  In the proof, we use a novel application of the discharging method to find a set of vertices for which any precoloring can be extended to the remainder of the graph using the probabilistic method.  Our result also makes progress towards Hadwiger&amp;apos;s Conjecture: we improve the best known bound on the chromatic number of $K_t$-minor free graphs by a constant factor.&#xd;
&#xd;
We provide a unified treatment of coloring graphs with small clique number.  We prove that for $\Delta$ sufficiently large, if $G$ is a graph of maximum degree at most $\Delta$ with list-assignment $L$ such that for each vertex $v\in V(G)$,&#xd;
$$|L(v)| \geq 72\cdot d(v)\min\left\{\sqrt{\frac{\ln(\omega(v))}{\ln(d(v))}}, \frac{\omega(v)\ln(\ln(d(v)))}{\ln(d(v))}, \frac{\log_2(\chi(G[N(v)]) + 1)}{\ln(d(v))}\right\}$$&#xd;
and $d(v) \geq \ln^2\Delta$, then $G$ is $L$-colorable.  This result simultaneously implies three famous results of Johansson from the 90s, as well as the following new bound on the chromatic number of any graph $G$ with $\omega(G)\leq \omega$ and $\Delta(G)\leq \Delta$ for $\Delta$ sufficiently large:&#xd;
$$\chi(G) \leq 72\Delta\sqrt{\frac{\ln\omega}{\ln\Delta}}.$$&#xd;
&#xd;
In Part~2, we introduce and develop the theory of fractional coloring with local demands.  A fractional coloring of a graph is an assignment of measurable subsets of the $[0, 1]$-interval to each vertex such that adjacent vertices receive disjoint sets, and we think of vertices ``demanding&amp;apos;&amp;apos; to receive a set of color of comparatively large measure.  We prove and conjecture ``local demands versions&amp;apos;&amp;apos; of various well-known coloring results in the $\omega, \Delta, \chi$ paradigm, including Vizing&amp;apos;s Theorem and Molloy&amp;apos;s recent breakthrough bound on the chromatic number of triangle-free graphs.&#xd;
&#xd;
The highlight of this part is the ``local demands version&amp;apos;&amp;apos; of Brooks&amp;apos; Theorem.  Namely, we prove that if $G$ is a graph and $f : V(G) \rightarrow [0, 1]$ such that every clique $K$ in $G$ satisfies $\sum_{v\in K}f(v) \leq 1$ and every vertex $v\in V(G)$ demands $f(v) \leq 1/(d(v) + 1/2)$, then $G$ has a fractional coloring $\phi$ in which the measure of $\phi(v)$ for each vertex $v\in V(G)$ is at least $f(v)$.  This result generalizes the Caro-Wei Theorem and improves its bound on the independence number, and it is tight for the 5-cycle.</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">graph coloring</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">list coloring</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">fractional coloring</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">probabilistic method</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">local version</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Reed&amp;apos;s Conjecture</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">clique number</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Cliques, Degrees, and Coloring: Expanding the ω, Δ, χ paradigm</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" 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>