An epsilon improvement to the asymptotic density of kcritical graphs Open Access
Larsen, Victor Olaf (2015)
Published
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 kcritical if X(G) = k but every proper subgraph has chromatic number less than k. As kcritical 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 kcritical graph on n vertices. The Ore construction, used to build larger kcritical graphs, implies that
fk(n + k  1) ≤ fk(n) + (k  1) [k/2  1/(k1)].
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/(k1)]
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 kcritical graph can be increased by ε > 0 by restricting to (Kk2)free kcritical graphs.
We also prove that the graphs constructible from the Ore construction and Kk, called kOre graphs, are precisely the graphs which attain Kostochka and Yancey's bound. Moreover, we also provide results regarding subgraphs which must exist in kOre graphs. For the discharging argument, carried out in two stages, we also prove results regarding the density of nearlybipartite subgraphs in kcritical graphs.
In the nal chapter we examine the minimal set of subgraphs, called kcritical structures, which one needs to forbid to obtain an ε increase in asymptotic density. This lays the groundwork for future research into asymptotic density in kcritical graphs.
Table of Contents
1 Introduction and history...1
1.1 Graph coloring...1
1.2 kcritical 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 Almostbipartite subgraphs in a kcritical
graph...13
2.3 Further edge bound on kcritical graphs...18
3 Ore compositions and kOre graphs...19
3.1 Ore composition and potential
function...20
3.2 Results on kOre 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 edgeadditions...32
4.4 Generalization to icollapsible and (i +
1)edgeadditions...38
5 Cloning...48
5.1 Clusters...48
5.2 Gadgets and Kk3 subgraphs...54
5.3 Bounds on degrees of neighbors of structurevertices...57
6 Discharging...61
6.1 Discharging: setup 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 kcritical structures...72
7.2 Preliminaries...74
7.3 Main result on kOre graphs...78
Bibliography...98
About this Dissertation
 Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School  

Department  
Degree  
Submission  
Language 

Research field  
Keyword  
Committee Chair / Thesis Advisor  
Committee Members 
Primary PDF
Thumbnail  Title  Date Uploaded  Actions 

An epsilon improvement to the asymptotic density of kcritical graphs ()  20180828 

Supplemental Files
Thumbnail  Title  Date Uploaded  Actions 

mydata.tex ()  20180828 


chapter2.tex ()  20180828 


discharging.tex ()  20180828 


OreCompAndkOre.tex ()  20180828 


CriticalExtensions.tex ()  20180828 


DefinitionsPrelims1.tex ()  20180828 


preamble.tex ()  20180828 


TG.fig ()  20180828 


IntroHistory.tex ()  20180828 


mythesis.tex ()  20180828 


cloning.tex ()  20180828 


thesis.bib ()  20180828 


TG2.fig ()  20180828 
