Given a graph G the chromatic number, denoted X(G), is smallest number of colors necessary to color V (G) such that no adjacent vertices receive the same color. A graph G is k-critical if X(G) = k but every proper subgraph has chromatic number less than k. As k-critical graphs can be viewed as minimal examples of graphs with chromatic number k, it is natural to ask how small such a graph can be.
Let fk(n) denote the minimum number of edges in a k-critical graph on n vertices. The Ore construction, used to build larger k-critical graphs, implies that
fk(n + k - 1) ≤ fk(n) + (k - 1) [k/2 - 1/(k-1)].
A recent paper by Kostochka and Yancey provides a lower bound for fk(n) which implies that the asymptotic density Φk := limn→∞ fk(n)/n = [k/2 - 1/(k-1)]
In this work, we use the method of discharging to prove a lower bound on the number of edges which includes structural information about the graph. This lower bound shows that the asymptotic density of a k-critical graph can be increased by ε > 0 by restricting to (Kk-2)-free k-critical graphs.
We also prove that the graphs constructible from the Ore construction and Kk, called k-Ore graphs, are precisely the graphs which attain Kostochka and Yancey's bound. Moreover, we also provide results regarding subgraphs which must exist in k-Ore graphs. For the discharging argument, carried out in two stages, we also prove results regarding the density of nearly-bipartite subgraphs in k-critical graphs.
In the nal chapter we examine the minimal set of subgraphs, called k-critical structures, which one needs to forbid to obtain an ε increase in asymptotic density. This lays the groundwork for future research into asymptotic density in k-critical graphs.
Table of Contents
1 Introduction and history...1
1.1 Graph coloring...1
1.2 k-critical graphs...3
1.3 History of fk(n)...4
2 Graph denitions and preliminaries...12
2.2 Almost-bipartite subgraphs in a k-critical graph...13
2.3 Further edge bound on k-critical graphs...18
3 Ore compositions and k-Ore graphs...19
3.1 Ore composition and potential
3.2 Results on k-Ore graphs...23
3.3 Diamonds and emeralds...25
4 Potential and critical extensions...28
4.2 Critical extensions...29
4.3 Collapsible sets and edge-additions...32
4.4 Generalization to i-collapsible and (i + 1)-edge-additions...38
5.2 Gadgets and Kk-3 subgraphs...54
5.3 Bounds on degrees of neighbors of structure-vertices...57
6.1 Discharging: set-up and rst stage...62
6.2 Second stage: averaging charge over the graph...66
7 Tcs(G), a modication of T(G)...71
7.1 k-critical structures...72
7.3 Main result on k-Ore graphs...78
About this Dissertation
|Committee Chair / Thesis Advisor|
|An epsilon improvement to the asymptotic density of k-critical graphs ()||2018-08-28||