\mychapter{Introduction and history}
\setcounter{page}{1}
%FORMATEDIT--THIS SHOULD FIX PAGE NUMBERING

\section{Graph coloring}
In this work, we assume that the reader has knowledge of basic concepts of graphs (formal definition, adjacency, connectivity, etc.).  
All non-standard terminology and notation will be specifically defined, but for any other definitions the reader can refer to a standard textbook such as \cite{G88}.
This work was inspired by recent developments concerning Ore's Conjecture \cite{O67} on $k$-critical graphs.
Let us briefly recall basic coloring definitions and then state Ore's Conjecture.

A \emph{$k$-coloring} $\phi$ of a graph $G$ is simply a labelling $\phi:V(G)\rightarrow [k]$.
If the coloring $\phi$ has the additional property that for every $uv\in E(G)$ $\phi(u)\neq\phi(v)$, then we say that the $k$-coloring is \emph{proper}.
If there is a proper $k$-coloring of a graph $G$, then we say that $G$ is \emph{$k$-colorable}.
Graph coloring has useful applications in scheduling, and in these applications we want to be as efficient as possible.
Although we can easily prove that every graph $G$ is $|V(G)|$-colorable, this is of no practical use.
Rather, we are concerned with the \emph{chromatic number} of a graph $G$, which is the smallest $k$ for which $G$ is $k$-colorable.
We denote the chromatic number of a graph $G$ by $\chi(G)$.

An early classic theorem regarding the chromatic number of a graph is Brooks' Theorem \cite{B41}.
Recall that $\Delta(G)$ is the maximum degree of a graph.
\begin{theorem}
If $G$ is a connected graph other than a complete graph or an odd cycle, then $\chi(G)\leq\Delta(G)$.
\end{theorem}
There is an obvious connection between the number of edges in a graph and the chromatic number of that graph.  As we add more edges, there
are more restrictions preventing an arbitrary $k$-coloring from being a proper $k$-coloring.  
Brooks' Theorem provides a bound on the chromatic number in terms of local density.
It is trivial to show that $\chi(G)\leq1+\delta(G)$ by making a greedy coloring argument.
Brooks' Theorem shows that we can be more efficient by 1 color class as long as $G$ is not a complete graph or an odd cycle.
For other classes of graphs, it is possible to be even more efficient.

The Borodin-Kostochka Conjecture \cite{BK77} is as follows.
\begin{conjecture}
If $G$ is a connected graph with $\omega(G)\leq\Delta(G)-1$ and $\Delta(G)\geq9$, then $\chi(G)\leq\Delta(G)-1$.
\end{conjecture}
Using the probabilistic method, this has been proven in \cite{R99} for very large $\Delta(G)$.

If we introduce further restrictions, we often obtain stronger results.  A graph $G$ is \emph{planar} if it can be embedded in a plane such that no edges are crossing.
A well-known coloring theorem for planar graphs is the celebrated Four Color Theorem \cite{AHK77}.
\begin{theorem}
Every planar graph is $4$-colorable.
\end{theorem}
This is of particular interest because the method of proof involves discharging, which is also the method used in this work.
Discharging involves assigning charge to a graph in a particular way (we assign charge to each vertex), moving the charge around using discharging rules and reducible configurations to find a contradiction. One can contradict any sort of global hypothesis such as planarity, an assumption on maximum average degree, or---as we do in this work---number of edges.

The original proof of the Four Color Theorem is famously complex, involving nearly 2,000 configurations.  That proof has been updated and streamlined to involve `only' 633 configurations \cite{RSST96} but still remains highly detailed.
The proof becomes much simpler, and the theorem stronger, if we introduce further restrictions on $G$.
Namely, all planar graphs which are triangle-free are $3$-colorable \cite{G59}.
In our work as well, we obtain a strengthening of previous results if we forbid certain subgraphs.
This is a common theme in the literature of coloring problems.



\section{$k$-critical graphs}
We return to the idea of density in a graph and its effect on the chromatic number.
Removing an edge from a graph takes away one obstacle for an arbitrary $k$-coloring to be a proper $k$-coloring.
Therefore, the chromatic number of $G-e$ is either $\chi(G)$ or $\chi(G)-1$.
The graphs we are concerned with are $k$-critical graphs.
A graph $G$ is \emph{$k$-critical} if $\chi(G)=k$ and every proper subgraph is $(k-1)$-colorable.
This is equivalent to requiring that $\chi(G-e)=\chi(G)-1$ for each edge $e\in E(G)$.

A natural example of a $k$-critical graph is $K_k$.  Also, using the Haj\'os construction (see \cite{W2001}, page 217) or the Ore composition (Definition \ref{def:OreComp}) one can combine any two $k$-critical graphs to create other $k$-critical graphs.
When studying coloring problems, the class of $k$-critical graphs is of particular interest as it is a natural starting point for general statements about $k$-chromatic graphs.
For example, if we could prove the Borodin-Kostochka conjecture for every $k$-critical graph then it would follow that it holds for all graphs.

From this perspective, we say that $k$-critical graphs are minimal examples of $k$-chromatic graphs.  It is natural to ask how small such graphs could be.
This leads to the study of the parameter $f_k(n)$, the minimum number of edges in a $k$-critical graph on $n$ vertices.
Ore's Conjecture \cite{O67} is the following.
\begin{conjecture}\label{conj:Ore}
If $k\geq4$, then
\[f_k(n+k-1)=f_k(n)+(k-1)\left(\frac{k}{2}-\frac{1}{k-1}\right).\]
\end{conjecture}
Another measure of a $k$-critical graph is the \emph{asymptotic density}, which we define to be $\displaystyle \phi_k:=\lim_{n\to\infty}\frac{f_k(n)}{n}$.
Ore's Conjecture \cite{O67}, if proven, would imply that the limit $\phi_k$ exists and that $\phi_k=\frac{k}{2}-\frac{1}{k-1}$.




\section{History of $f_k(n)$}

We want to survey the history of bounds on $f_k(n)$.  The first natural bound comes from a connectivity argument.  Clearly $\delta(G)\geq k-1$ for any $k$-critical graph (or a greedy coloring will properly $(k-1)$-color $G$) so therefore
\[f_k(n)\geq\frac{k-1}{2}n.\]
In terms of asymptotic density, this shows that, if the limit $\phi_k$ exists then $\phi_k\geq\frac{k}{2}-\frac{1}{2}$ for $k$-critical graphs.
Throughout the literature there have been many improvements on bounds for $f_k(n)$; however, we will focus our attention on $\phi_k$.

The reason for examining $\phi_k$ comes from an observation about the Haj\'{o}s construction (see \cite{W2001}, page 217). Given a $k$-critical graph $G$, if we look at the graph $G'$ resulting from a Haj\'{o}s construction of $G$ and $K_k$, then we have added $k-1$ vertices and added one less than the number of edges in a $K_k$.  That is,
\[|V(G')|=|V(G)|+k-1\text{ and }|E(G')|=|E(G)|+\frac{(k-2)(k+1)}{2}.\]
It follows that $f_k(n+k-1)\leq f_k(n)+\frac{(k-2)(k+1)}{2}$, which implies that $\phi_k$ exists and that
\[\phi_k\leq \frac{1}{k-1}\left(\frac{(k-2)(k+1)}{2}\right)=\frac{k}{2}-\frac{1}{k-1}.\]
This observation led Ore to pose Conjecture \ref{conj:Ore}.
Thus, it follows that $\frac{k}{2}-\frac{1}{2}\leq\phi_k\leq \frac{k}{2}-\frac{1}{k-1}$.

The first improvement to the lower bound on $f_k(n)$ came in 1957 when Dirac \cite{D57} showed that $f_k(n)\geq\frac{k-1}{2}n+\frac{k-3}{2}$ for $k\geq4$ and $n\geq k+2$.
When $n\neq 2k-1$, Kostochka and Stiebitz \cite{KS99} obtain the improvement
\[f_k(n)\geq\frac{k-1}{2}n+k-3.\]
Both of these results are significant in their own right, but in terms of asymptotic density of a $k$-critical graph these results offer no improvement over the first bound obtained by a connectivity argument.

Gallai \cite{G63} was able to improve the lower bound on asymptotic density, as well as calculate many exact values for $f_k(n)$.  The bound he gives for $k\geq4$ and $n\geq k+2$ is $f_k(n)\geq\frac{k-1}{2}n+\frac{k-3}{2(k^2-3)}n$.
This was further improved to
\[f_k(n)\geq\frac{k-1}{2}n+\frac{k-3}{2(k^2-2k-1)}n\]
by Krivelevich \cite{K97}.
Although these results bring the lower bound on $\phi_k$ closer to the upper bound, as $k$ grows this improvement diminishes.

Ore's Conjecture was proven to be asymptotically true in a recent paper by Kostochka and Yancey \cite{KY2014}.  They show the following result.
\begin{theorem}\label{thm:Theirs}
If $k\geq4$ and $G$ is $k$-critical then 
\[|E(G)|\geq\left\lceil\frac{(k+1)(k-2)|V(G)|-k(k-3)}{2(k-1)}\right\rceil.\]
\end{theorem}
Note that $\frac{(k+1)(k-2)}{2(k-1)}=\frac{k}{2}-\frac{1}{k-1}$, so Ore's Conjecture is asymptotically true.
In a subsequent work \cite{KY2015}, they verified that the graphs which attain this bound are exactly the $k$-Ore graphs (defined in Chapter 3).
The method of proof of Theorem \ref{thm:Theirs} is to define a \emph{potential function} which is a measure of density in the graph.  By bounding the potential of a $k$-critical graph using a discharging argument, they obtain a bound on the number of edges as a corollary.
The proof in this work mirrors the proof of Theorem \ref{thm:Theirs}, with significant modifications to account for the extra information we give on the structure of $k$-critical graphs.
Our aim is to increase asymptotic density past the upper bound of $\frac{k}{2}-\frac{1}{k-1}$ and to do this, we must forbid certain subgraphs.  In Chapters 2--6, we lay out a proof which yields an improvement for $(K_{k-3})$-free $k$-critical graphs.

A similar attempt to push asymptotic density above the bound given by Ore's Conjecture was made by Postle \cite{P2014} in the case where $k=4$.  For a $4$-critical graph $G$, Theorem \ref{thm:Theirs} implies that $|E(G)|\geq\frac{5}{3}|V(G)|-\frac{2}{3}$.  However, in \cite{P2014} it is shown that 
there exists an $\epsilon>0$ such that
\begin{equation}\label{eq:Luke4}
|E(G)|\geq\left(\frac{5}{3}+\epsilon\right)|V(G)|
\end{equation}
when $G$ is a $4$-critical graph with girth at least 5.
It can be shown that, in order to obtain any improvement in the asymptotic density, $\{K_3,C_4\}$ is, in fact, a minimal set of graphs one needs to forbid as subgraphs.
For $k$-critical graphs with $k>4$, a minimal set of subgraphs which we must forbid to obtain an improvement in asymptotic density is the set of \emph{$k$-critical structures} (Definition \ref{def:kCritStruc}).
In Chapter 7, we examine a bound on these $k$-critical structures in $k$-Ore graphs.
However, an analogous result to Equation \ref{eq:Luke4} using $k$-critical structures for $k>4$ cannot be obtained through the methods of this work.




\section{Results}

We now briefly summarize the results of this work and their implications.
The most significant result of this paper is a strengthening of the conclusion of Theorem \ref{thm:Theirs}.
We make a modification to the potential function which includes the function $T(G)$ (see Definition \ref{def:TGdefin}) which counts, in a particular way, the $K_{k-2}$ and $K_{k-1}$ subgraphs of a graph $G$.

Below is the precise formulation of the potential function used in this work to prove results on $k$-critical graphs for a fixed $k$.  This is examined in depth in Chapter 4.

{\noindent\bf Definition \ref{def:Potential}}
{\it Given a graph $G$, we define the \emph{potential} of a graph to be
\[\rho_\epsilon(G):=\left((k-2)(k+1)+\epsilon\right)|V(G)|-2(k-1)|E(G)|-\delta T(G)\]
for a fixed epsilon with $0\leq\epsilon\leq\frac{4}{k^3-2k^2+3k}$ and $\delta=(k-1)\epsilon$.
}
Because $\epsilon$ remains fixed throughout the proof, we omit this subscript.  
Using this new potential function, we are able to prove (for any $0\leq\epsilon\leq\frac{4}{k^3-2k^2+3k}$) the following theorem via a discharging argument.  The reader can find a definition of $k$-Ore graph in Chapter 3.

{\noindent\bf Theorem \ref{thm:main}}
{\it If $G$ is a $k$-critical graph with $k\geq4$ then 
\begin{enumerate}
\item $\rho(G)=k(k-3)+k\epsilon-2\delta$ if $G=K_k$,
\item $\rho(G)\leq k(k-3)+|V(G)|\epsilon-\left(2+\frac{|V(G)|-1}{k-1}\right)\delta$ if $G$ is $k$-Ore and $G\neq K_k$, and
\item $\rho(G)\leq k(k-3) -2(k-1)$ if $G$ is not $k$-Ore, for $k\geq33$.
\end{enumerate}
}

On its own, this result is slightly opaque so we highlight important corollaries below.
\begin{corollary}\label{cor:MainStuff}
If $k\geq33$ and $G$ is $k$-critical then
\[|E(G)|\geq\left\lceil\frac{\left((k+1)(k-2)+\epsilon\right)|V(G)|-k(k-3)+2\delta-k\epsilon-\delta T(G)}{2(k-1)}\right\rceil\]
where $\epsilon\leq\frac{4}{k^3-2k^2+3k}$ and $\delta=(k-1)\epsilon$.
\end{corollary}
Note that by setting $\epsilon=0$, we get the same result as Theorem \ref{thm:Theirs}, although there is an extra restriction on $k$.
Importantly, this gives us structural information about the graphs which realize or approach the lower bound on $\phi_k$ given by Theorem \ref{thm:Theirs}.
Graphs which have fewer $K_{k-2}$ subgraphs and are close to the bound will have, in general, more edges than those with many $K_{k-2}$ subgraphs.

In fact, if $G$ is a $(K_{k-2})$-free $k$-critical graph, then $T(G)=0$ and we have shown the following result.
Let $\overline{f}_k(n)$ be the minimum number of edges in a $(K_{k-2})$-free $k$-critical graph on $n$ vertices.
\begin{corollary}
The asymptotic density $\overline{\phi}_k:=\lim_{n\to\infty}\frac{\overline{f}_k(n)}{n}$ of $(K_{k-2})$-free $k$-critical graphs is
bounded below by
\[\overline{\phi}_k\geq \frac{(k-2)(k+1)+\epsilon}{2(k-1)}\]
where $\epsilon\leq\frac{4}{k^3-2k^2+3k}$.
\end{corollary}

If we restrict our attention to $k$-Ore graphs then Corollary \ref{cor:MainStuff} holds for $k\geq4$ rather than just $k\geq33$.
Therefore, the structural implications of Corollary \ref{cor:MainStuff} hold for the family of $k$-Ore graphs even with smaller $k$.
However, we are not able to obtain any increase in asymptotic density on this set of graphs because, by Lemma \ref{lem:kOreAwayFromVertex}, there are no $k$-Ore graphs which are $(K_{k-2})$-free.
In Chapter 7, we explore a second new definition of potential function.  Instead of $T(G)$, we introduce the counting function $T_{cs}(G)$ which counts $k$-critical structures, which is a minimal set of subgraphs we must forbid to see an increase in asymptotic density.
This yields the following result.

{\noindent\bf Theorem \ref{thm:Main2}}
{\it If $G$ is $k$-Ore and $k\geq4$ then for $a=7(k-1)$ the following is true.
\begin{enumerate}
 \item If $T_{cs}(G)\geq3$ then $T_{cs}(G)-2\geq\frac{|V(G)|-1}{2a}$ and 
 \item if $T_{cs}(G)\leq2$ then $a\geq|V(G)|$.
\end{enumerate}
}
The first statement of Theorem \ref{thm:Main2} is similar to the bound which gives the coefficient of $\delta$ in the second statement of Theorem \ref{thm:main}.
This observation gives hope that a theorem analogous to Theorem \ref{thm:Main2} which uses $T_{cs}(G)$ rather than $T(G)$ could be proven.
However, such an endeavor is beyond the scope of this work.


When we restrict our attention to $k$-critical graphs which are not $k$-Ore, a stronger statement than Corollary \ref{cor:MainStuff} is possible.
This is also a corollary to Theorem \ref{thm:main}.
\begin{corollary}
If $k\geq33$ and $G$ is a $k$-critical graph which is not $k$-Ore then
\[|E(G)|\geq\left\lceil\frac{\left((k+1)(k-2)+\epsilon\right)|V(G)|-k(k-3)-\delta T(G)}{2(k-1)}\right\rceil+1\]
where $\epsilon\leq\frac{4}{k^3-2k^2+3k}$ and $\delta=(k-1)\epsilon$.
\end{corollary}
If we set $\epsilon=0$, this proves that $k$-critical graphs which are not $k$-Ore have at least one edge more than the bound given by Theorem \ref{thm:Theirs}.
Therefore this work independently verifies the result of \cite{KY2015}, that the graphs which attain the bound in Theorem \ref{thm:Theirs} are exactly the $k$-Ore graphs.



Theorem \ref{thm:main} is the main result of this work.  The first statement of the theorem is a straightforward calculation using the definition of potential and the second statement requires a lemma (Lemma \ref{lem:TGkOre}) about how $T(G)$ behaves for $k$-Ore graphs.  The rest of this work (excepting the final chapter) focuses on proving the third statement---which is the most complex of the three---via a discharging argument which is split up into two stages.  In the method of discharging, each vertex is given initial charge relative to its degree.  The assumption that $G$ is a minimal counterexample to the third statement of Theorem \ref{thm:main} implies that the total charge on the graph is positive.  Therefore, there must be vertices in $V(G)$ whose initial charge is positive (we say that these vertices are \emph{unsatisfied}); this is exactly the vertices of degree $k-1$.  To move towards a contradiction, we will create rules by which high degree vertices send charge to neighbors of degree $k-1$ while still retaining negative charge for themselves.  Not all vertices can be satisfied in this way, so we finish with a second round of discharging.

In Chapter 2, we begin by looking at bounds on the number of edges from an independent set $I\subseteq V(G)$ of degree $k-1$ vertices in a $k$-critical graph $G$.  This requires looking at kernel-perfect directed graphs and list-coloring arguments.  We also state a result by Kierstead and Rabern \cite{KR2014} which is used to finish the discharging argument.

In Chapter 3, we define $k$-Ore graphs and the Ore composition operation.  We then prove the first two statements of Theorem \ref{thm:main}.
We also introduce some structural lemmas about subgraphs that must exist in $k$-Ore graphs, which we use in the following chapters.

In Chapter 4, we begin our thorough investigation of the potential function $\rho$.
Corollary \ref{cor:ExtensionDrop} implies that every proper induced subgraph $G[R]\subsetneq G$ has potential that is higher than $\rho(G)$.  Therefore $\rho(G)=\min\{\rho_G(R)\mid R\subseteq V(G)\}$, and we are able to use $\rho$ as a global parameter for discharging.
Because discharging arguments make a global assumption and then examine specific local structures, it is crucial for this global assumption to also hold on all induced subgraphs.
The main goal of this chapter is to establish Lemma \ref{lem:TightGeneralEdgeAddition}, which is used in determining the local structure near vertices of degree $k-1$ in a minimal counterexample to the third statement of Theorem \ref{thm:main}.
This will help inform the rules in the first stage of discharging.

In Chapter 5, we classify all vertices of degree $k-1$ into three different categories, depending on their local structure.
The main lemma is Lemma \ref{lem:CloningGivesGadget} which shows that any adjacent vertices of degree $k-1$ must give rise to one of two structures, each of which has enough charge to compensate for the degree $k-1$ vertices near it.

In Chapter 6, we complete the proof by discharging in two stages.  In the first stage, we ensure that two classes of degree $k-1$ vertices are satisfied.  The third class cannot be directly satisfied this way so in the second stage, we examine the total charge on the graph and use it to get a bound on $|E(G)|$.  From our assumption on potential and the result by Kierstead and Rabern, we have two other bounds on $|E(G)|$.
These bounds cannot be simultaneously satisfied and we complete the proof of Theorem \ref{thm:main}.

In Chapter 7, which is self-contained, we examine $k$-Ore graphs under a different definition of potential.
We exclude different structures from $k$-critical graphs $G$, which gives more information about the structure of $k$-Ore graphs.
These structures, called \emph{$k$-critical structures}, are the minimal set of subgraphs which we have to forbid to obtain an $\epsilon$ improvement in the asymptotic density $\phi_k$ for $k$-critical graphs and thus the proof of Theorem \ref{thm:Main2} is far from straightforward.
Without increasing the complexity far beyond the scope of this work, we cannot extend these results to general $k$-critical graphs.

