An epsilon improvement to the asymptotic density of k-criticalgraphs Público
Larsen, Victor Olaf (2015)
Abstract
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
1.4 Results...6
2 Graph denitions and preliminaries...12
2.1 Denitions...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 function...20
3.2 Results on k-Ore graphs...23
3.3 Diamonds and emeralds...25
4 Potential and critical extensions...28
4.1 Potential...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 Cloning...48
5.1 Clusters...48
5.2 Gadgets and Kk-3 subgraphs...54
5.3 Bounds on degrees of neighbors of structure-vertices...57
6 Discharging...61
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.2 Preliminaries...74
7.3 Main result on k-Ore graphs...78
Bibliography...98
About this Dissertation
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Palavra-chave | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
An epsilon improvement to the asymptotic density of k-criticalgraphs () | 2018-08-28 12:51:37 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
mydata.tex () | 2018-08-28 12:51:54 -0400 |
|
|
|
chapter2.tex () | 2018-08-28 12:52:03 -0400 |
|
|
|
discharging.tex () | 2018-08-28 12:52:11 -0400 |
|
|
|
OreCompAndkOre.tex () | 2018-08-28 12:52:20 -0400 |
|
|
|
CriticalExtensions.tex () | 2018-08-28 12:52:26 -0400 |
|
|
|
DefinitionsPrelims1.tex () | 2018-08-28 12:52:34 -0400 |
|
|
|
preamble.tex () | 2018-08-28 12:52:42 -0400 |
|
|
|
TG.fig () | 2018-08-28 12:52:53 -0400 |
|
|
|
IntroHistory.tex () | 2018-08-28 12:52:59 -0400 |
|
|
|
mythesis.tex () | 2018-08-28 12:53:08 -0400 |
|
|
|
cloning.tex () | 2018-08-28 12:53:14 -0400 |
|
|
|
thesis.bib () | 2018-08-28 12:53:18 -0400 |
|
|
|
TG2.fig () | 2018-08-28 12:53:21 -0400 |
|