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

Larsen, Victor Olaf (2015)

Permanent URL:


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


About this Dissertation

Rights statement
  • 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.
  • English
Research field
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files