Cliques, Degrees, and Coloring: Expanding the ω, Δ, χ paradigm

graph coloring;list coloring;fractional coloring;probabilistic method;local version;Reed's Conjecture;clique number

Kelly, Thomasaffiliation1:Faculty of Mathematics ; advisor:Postle, Luke ; Postle, Luke ;

University of Waterloo

关键词: Reed'    s Conjecture;    local version;    graph coloring;    list coloring;    clique number;    fractional coloring;    probabilistic method;    Doctoral Thesis;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/14862/1/Kelly_Thomas.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Many of the most celebrated and influential results in graph coloring, such as Brooks' Theorem and Vizing's Theorem, relate a graph'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's $omega, Delta, chi$ Conjecture, follow this theme.This thesis both broadens and deepens this classical paradigm.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.We conjecture the ``list-local version'' of Reed's Conjecture, that is every graph is $L$-colorable if $L$ is a list-assignment such that $$|L(v)| geq lceil (1 - varepsilon)(d(v) + 1) + varepsilonomega(v))ceil$$for each vertex $v$ and $varepsilon leq 1/2$, and we prove this for $varepsilon leq 1/330$ under some mild additional assumptions.We also conjecture the ``$mathrm{mad}$ version'' of Reed's Conjecture, even for list-coloring.That is, for $varepsilon leq 1/2$, every graph $G$ satisfies$$chi_ell(G) leq lceil (1 - varepsilon)(mad(G) + 1) + varepsilonomega(G)ceil,$$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's Conjecture: we improve the best known bound on the chromatic number of $K_t$-minor free graphs by a constant factor.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 $vin V(G)$,$$|L(v)| geq 72cdot d(v)minleft{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))}ight}$$and $d(v) geq ln^2Delta$, 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:$$chi(G) leq 72Deltasqrt{frac{lnomega}{lnDelta}}.$$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'' to receive a set of color of comparatively large measure.We prove and conjecture ``local demands versions'' of various well-known coloring results in the $omega, Delta, chi$ paradigm, including Vizing's Theorem and Molloy's recent breakthrough bound on the chromatic number of triangle-free graphs.The highlight of this part is the ``local demands version'' of Brooks' Theorem.Namely, we prove that if $G$ is a graph and $f : V(G) ightarrow [0, 1]$ such that every clique $K$ in $G$ satisfies $sum_{vin K}f(v) leq 1$ and every vertex $vin 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 $vin 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.