# An epsilon improvement to the asymptotic density of k-critical graphs Open Access

## Larsen, Victor Olaf (2015)

Permanent URL: https://etd.library.emory.edu/concern/etds/n009w275v?locale=en
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 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.

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.4 Generalization to i-collapsible and (i + 1)-edge-additions...38

5 Cloning...48

5.1 Clusters...48
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