\mychapter{Ore compositions and $k$-Ore graphs}

We can equivalently define a $k$-critical graph to be a graph $G$ with chromatic number $k$ such that every proper subgraph of $G$ has chromatic number at most $k-1$.
In this sense, $k$-critical graphs can be thought of as minimal graphs that are not $(k-1)$-colorable.  
It is natural to ask how small such graphs can be. 
Recall that $f_k(n)$ is the minimum number of edges of a $k$-critical graph on $n$ vertices.
In a recent paper, Kostochka and Yancey \cite{KY2014} proved that a $k$-critical graph must have edge density above a certain threshold.  
Namely, they proved that if $k\geq 4$, $n\geq k$ and $n\neq k+1$ then
\[f_k(n)\geq\left\lceil\left(\frac{k}{2}-\frac{1}{k-1}\right)n-\frac{k(k-3)}{2(k-1)}\right\rceil.\]
Further, this bound is tight since it is attained by an infinite class of $k$-critical graphs.
In a subsequent paper, Kostochka and Yancey \cite{KY2015} proved that $k$-critical graphs which attain these bounds are precisely the \emph{$k$-Ore graphs} described below.
Therefore, in exploring new bounds on edge-density of $k$-critical graphs, it is important to begin our discussion with results on $k$-Ore graphs.


\section{Ore composition and potential function}

\begin{definition}\label{def:OreComp}
An \emph{Ore composition} of two graphs $G_1$ and $G_2$ is a graph obtained by the following procedure:
\begin{enumerate}
	\item delete an edge $xy$ from $G_1$,
	\item split some vertex $z$ of $G_2$ into two vertices $z_1$ and $z_2$ of positive degree,
	\item identify $x$ with $z_1$ and identify $y$ with $z_2$.
\end{enumerate}
\end{definition}
Note that an Ore composition of $G_1$ and $G_2$ does not necessarily obtain a unique graph. Further, the order in which we list the graphs is important; we say that $G_1$ (always listed first) is the $\emph{edge-side}$ and $G_2$ (always listed second) is the \emph{split-side} of the composition.
The identified vertices $\underline{xz_1}$ and $\underline{yz_2}$ are the \emph{overlap} vertices of the composition.
Further, we say that $xy$ is the \emph{replaced edge} of $G_1$ and that $z$ is the \emph{split vertex} of $G_2$.
A graph $G$ is a \emph{$k$-Ore graph} if and only if it is in the smallestclass of graphs which is closed under the Ore composition operation and contains $K_k$.  This means that any $k$-Ore graph can be obtained if we start with $K_k$ and make repeated Ore compositions with copies of $K_k$ and any intermediate graphs created along the way.

On occasion, we are interested in decomposing a $k$-Ore graph $G$ into the graphs $G_1$ and $G_2$ that were used to obtain $G$.  When we split a vertex $z$ of the split-side, the resulting graph can be properly $(k-1)$-colored, but the new vertices $z_1$ and $z_2$ must receive different colors.  Therefore, if we focus on colorings of $G_1$ then the restrictions caused by the replaced edge $xy\in E(G_1)$ are the same as the restrictions caused by the split-side of the composition.
We may view the graph $G$ as a graph $G'$ isomorphic to $G_1$ where the edge $xy\in E(G')$ corresponds to a subgraph $D\subseteq G$ which is the split-side of the Ore composition of $G$ after the vertex $z$ has been split into two vertices.
We call the edge $xy\in E(G')$ an \emph{edge-replacement} to distinguish it from the edges which are in both $G$ and $G_1$.
Replacing an edge-replacement $e$ in $G'$ with its corresponding subgraph $D\subseteq G$ is equivalent to taking an Ore composition of $G'$ and $D/\underline{xy}$.

\begin{proposition}\label{prp:ReducedOre}
Suppose that $G$ is a $k$-Ore graph.  Then there exists a graph $H=K_k$ with $\ell$ edge-replacements $\{e_1,\ldots,e_\ell\}$ corresponding to subgraphs $\{D_1,\ldots,D_\ell\}$ of $G$.  The graph $G$ can be obtained from $H$ by replacing each $e_i$ with $D_i$.
\end{proposition}
\begin{proof}
Let $G$ be a $k$-Ore graph.
We will prove this by induction on $|V(G)|$.
If $G$ is $K_k$ then the result is trivial, so we may assume that $G$ is the Ore composition of two $k$-Ore graphs $G_1$ and $G_2$ with overlap vertices $\{x,y\}$.
Let $D\subseteq G$ be the subgraph $G[(V(G)-V(G_1))\cup\{x,y\}]$.  This subgraph is isomorphic to the $k$-Ore graph $G_2$ after the split-vertex $z$ is split into two vertices $x,y$ of positive degree.

By induction $G_1$ can be reduced to $H_1=K_k$ where the graph $H_1$ has $r$ edge-replacements.
Suppose that $xy$ is an actual edge in $H_1$. Then $G$ is reducible to $H=K_k$ where $H$ has the same $r$ edge-replacements as $H_1$ and also has the edge-replacement $xy$ corresponding to $D$.
Suppose instead that $xy$ is not an edge in $H_1$. Then $xy$ is an edge in a subgraph $D_1\subseteq G_1$ which corresponds to an edge-replacement $e_1$ in $H_1$.
Now $G$ is reducible to $H=K_k$ where $e_1$ is an edge-replacement corresponding to a subgraph which is an Ore composition of $D_1$ and $G_2$.
\end{proof}

Kostochka and Yancey's bound on $f_k(n)$ also gave an asymptotic confirmation of Ore's Conjecture; that is, Kostochka and Yancey's result proves that $\varphi_k:=\lim_{n\to\infty}\frac{f_k(n)}{n}=\frac{k}{2}-\frac{1}{k-1}$.
One of the goals of this work is to increase the asymptotic density when $k\geq33$ for the class of $k$-critical graphs that do not contain $K_{k-2}$ as a subgraph, which leads to a strengthening of Kostochka and Yancey's result.
%or somehow informs teh structure of k-critical graphs in general

In order to obtain this improvement, we define a graph function $T$ which `counts' the $K_{k-1}$ and $K_{k-2}$ subgraphs in a particular way.
\begin{definition}\label{def:TGdefin}
Suppose that the graph $H$ is a disjoint union of $r$ $K_{k-1}$ and $s$ $K_{k-2}$ subgraphs.  Then $T(H)$ is defined to be $2r+s$.
More generally, we define $T(G)$ for an arbitrary graph $G$ as follows:
\[T(G):=\max_{H\subseteq G}\{T(H)\mid H\text{ is a disjoint union of }K_{k-1}\text{ and }K_{k-2}\text{ components}\}.\]
\end{definition}

We let $T(G)$ be the maximum over all choices of subgraphs $H\subseteq G$ which are disjoint collections of $K_{k-1}$ and $K_{k-2}$ subgraphs.  For example, for $k=5$, Figure \ref{fig:TG} shows two subgraphs $H_1$ and $H_2$ of $G$.  Both $T(H_1)$ and $T(H_2)$ are 2 and so it follows that $T(G)\geq 2$ (in fact, we can check that $T(G)=2$ in this example).  These two choices of subgraphs also highlight that there could be multiple subgraphs $H\subseteq G$ which witness $T(G)$.  Throughout our proofs, we make no assumptions on how these subgraphs are chosen.
\begin{figure}\label{fig:TG}
\begin{center}
\includegraphics[width=.4\linewidth]{TG}
\hspace{40pt}
\includegraphics[width=.4\linewidth]{TG2}
\end{center}
\caption{$H_1\subseteq G$ is in bold on the left; $H_2\subseteq G$ is in bold on the right.}
\end{figure}

We can now define the potential of a graph.  
\begin{definition}\label{def:Potential}
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$.
\end{definition}
Because $\epsilon$ remains fixed throughout the proof, we omit this subscript.  The theorem is then proven for any potential function $\rho_\epsilon$ with $\epsilon$ in the specified range.  Different values of $\epsilon$ in this range will lead to different corollaries, as discussed in Chapter 1.
The main goal of this work, and the aim of the remainder of this chapter and the subsequent three chapters, is to prove the following theorem about potential of $k$-critical graphs:

\begin{theorem}\label{thm:main}
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}
\end{theorem}

When $k\geq33$, this is a complete statement about potentials for all $k$-critical graphs.  For $k<33$ the first two statements hold but, due to constraints in the discharging argument that we use in Chapter 6, we are not able to prove the third statement for small $k$ without significantly increasing the complexity of the discharging arguments.
Note that $T(K_k)=2$ and so the first assertion of Theorem \ref{thm:main} is immediate from the definition of $\rho(G)$.  In the following Section, we will examine the function $T(G)$ where $G$ is a $k$-Ore graph or an Ore composition and we will prove the second assertion of Theorem \ref{thm:main}.  %In sections 3-??, we complete the proof of the main theorem.



\section{Results on $k$-Ore graphs}

First, we prove the following lemma about Ore compositions:

\begin{lemma}\label{lem:TGcompose}
If $G$ is an Ore composition of $G_1$ and $G_2$, then $T(G)\geq T(G_1)+ T(G_2)-2$. Moreover, if $G_1=K_k$ or $G_2=K_k$ then $T(G)\geq T(G_1)+T(G_2)-1$.
\end{lemma}
\begin{proof}
Suppose that $G$ is an Ore composition of $G_1$ and $G_2$ .
Let $e$ be the replaced edge of $G_1$ and $z$ be the split vertex of $G_2$.  From the definition of an Ore composition $T(G)\geq T(G_1-e)+T(G_2-\{z\})$.  
Note that $T(G_1-e)\geq T(G_1)-1$ and $T(G_2-\{z\})\geq T(G_2)-1$, because removing a single element can decrease $T(G)$ by at most 1.
Thus, we get $T(G)\geq T(G_1)+T(G_2)-2$ as desired.  
If $G_1=K_k$ then $T(K_k-e)=2$ for every edge $e\in E(G_1)$; also, if $G_2=K_k$ then $T(K_k-\{v\})=2$ for every $v\in V(G_2)$.
Removing an element from a $K_k$ graph does not decrease $T(K_k)$.
Therefore, it follows that $T(G)\geq T(G_1)+T(G_2)-1$ if either $G_1$ or $G_2$ is $K_k$.
Further, if both $G_1$ and $G_2$ are $K_k$ then $T(G)=4$.
\end{proof} 

Let $G$ be a $k$-Ore graph.  We can show inductively that there exists an $\ell\geq0$ such that $|V(G)|=k+\ell(k-1)$ and $|E(G)|=\frac{(\ell+1)k(k-1)}{2}-\ell$.  When $G$ is a $k$-Ore graph that is not $K_k$, then it is an Ore composition and we can use Lemma \ref{lem:TGcompose} to get a bound on $T(G)$.

\begin{lemma}\label{lem:TGkOre}
If $G$ is a $k$-Ore graph and $G\neq K_k$ then $T(G)\geq 2+\frac{|V(G)|-1}{k-1}$.
\end{lemma}
\begin{proof}
We proceed by induction on $|V(G)|$.
%really I'm induction on $\ell$.
Since $G$ is $k$-Ore and $G\neq K_k$, then $G$ must be the Ore composition of two $k$-Ore graphs $G_1$ and $G_2$.
Note that if $G$ is an Ore composition of $G_1$ and $G_2$ then, by the definition of Ore composition, $|V(G)|=|V(G_1)|+|V(G_2)|-1$
If $G_1$ and $G_2$ are both $K_k$ graphs, then $|V(G)|=2k-1$ so we need to show that $T(G)\geq4$. 
 We know that $T(K_k-e)=T(K_k-\{z\})=2$ regardless of the choice of replaced edge $e$ and split vertex $z$ in the composition.  
 Thus $T(G)\geq4$ as desired.
 
Suppose that $G_1=K_k$ and $G_2\neq K_k$.  
Then by Lemma \ref{lem:TGcompose} and the inductive hypothesis, we have that 
\[T(G)\geq T(G_2)+1\geq \left(2+\frac{|V(G_2)|-1}{k-1}\right)+1 =2+\frac{|V(G)|-1}{k-1}\]
as desired.
A similar argument covers the case where $G_1\neq K_k$ and $G_2=K_k$.

Finally, suppose that neither $G_1$ nor $G_2$ is $K_k$.
Then because $|V(G)|=|V(G_1)|+|V(G_2)|-1$, it follows from Lemma \ref{lem:TGcompose} that 
\[T(G)\geq \left(2+\frac{|V(G_1)|-1}{k-1}\right)+\left(2+\frac{|V(G_2)|-1}{k-1}\right)-2=\left(2+\frac{|V(G)|-1}{k-1}\right).\]
\end{proof}

We obtain the second assertion of Theorem \ref{thm:main} as a corollary.
\begin{corollary}
If $G$ is a $k$-critical graph that is $k$-Ore and $G\neq K_k$ then $\rho(G)\leq k(k-3)+|V(G)|\epsilon-\left(2+\frac{|V(G)|-1}{k-1}\right)\delta$.
\end{corollary}
\begin{proof}
To prove this, we recall that
\[\rho(G):=\left((k-2)(k+1)+\epsilon\right)|V(G)|-2(k-1)|E(G)|-\delta T(G).\]
  Also, a $k$-Ore graph which is not $K_k$ has $k+\ell(k-1)$ vertices and $\frac{(\ell+1)k(k-1)}{2}-\ell$ edges for some $\ell\geq1$.
  Therefore, using Lemma \ref{lem:TGkOre}, it is a straightforward calculation to show that $\rho(G)\leq k(k-3)+|V(G)|\epsilon-\left(2+\frac{|V(G)|-1}{k-1}\right)\delta$.
\end{proof}


\section{Diamonds and emeralds}
\begin{definition}\label{def:Diamond}
A subgraph $D\subseteq G$ is a \emph{diamond of $G$} if $D=K_k-uv$  and $\deg_G(x)=k-1$ for each $x\in V(D)-\{u,v\}$.  The vertices $u$ and $v$ are called the \emph{endpoints} of the diamond.
\end{definition}
\begin{definition}
A subgraph $D\subseteq G$ is an \emph{emerald of $G$} if $D=K_{k-1}$  and $\deg_G(x)=k-1$ for each $x\in V(D)$.
\end{definition}

\begin{lemma}\label{lem:kOreAwayFromVertex}
If $G$ is $k$-Ore and $v\in V(G)$, then there exists a diamond or emerald of $G$ not containing $v$.  %POSSIBLY ALSO AWAY FROM AN EDGE
\end{lemma}
\begin{proof}
We will prove this by induction on the order of $G$, $|V(G)|$. Let $G$ be a $k$-Ore graph and let $v\in V(G)$ be an arbitrary vertex.  If $G=K_k$ then $G-\{v\}$ is an emerald of $G$ not containing $v$.
Otherwise, we have that $G$ is an Ore composition of two $k$-Ore graphs $G_1$ and $G_2$ with overlap vertices $\{a,b\}$.  We choose this composition to minimize the number of vertices in the edge-side $G_1$.  If $v\in V(G_1)$ then, inductively, there is a diamond or an emerald $D$ in $G_2$ not containing the vertex $\underline{ab}\in V(G_2)$.  Note that $D$ is also a diamond or emerald of $G$ not containing $v$.  

Therefore, we may assume that $v\in V(G_2)-V(G_1)$.  If $G_1=K_k$, then $G_1$ is a diamond of $G$ and we are done.  Otherwise, $G_1$ is a composition of two $k$-Ore graphs $H_1$ and $H_2$ with overlap vertices $\{x,y\}$.  If the edge $ab\in E(G_1)$ is in $E(H_2)$ then there is a decomposition of $G$ with $H_1$ as the edge-sde, which contradicts the minimality of $G_1$.  
Thus, $ab\in E(H_1)$ and by induction there is a subgraph $D$ of $H_2$ which is a diamond or emerald not containing $\underline{xy}\in V(H_2)$.  Note that $D$ is also disjoint from vertex $v$, and is also a diamond or emerald in $G$ because $ab\in E(H_1)$.  This completes the proof.
\end{proof}

Note that one could prove as a corollary that there is a diamond or emerald in $G$ disjoint from any edge $e\in E(G)$.

\begin{lemma}\label{lem:kOreAwayFromSet}
If $G$ is $k$-Ore and $D=K_{k-1}$ is a subgraph of $G$, then either $G= K_k$ or there exists a diamond or emerald in $G$ disjoint from $D$.
\end{lemma}
\begin{proof}
We will prove this by induction on $|V(G)|$.  Let $G$ be a $k$-Ore graph and let $D=K_{k-1}$ be a subgraph of $G$. If $G=K_k$ then we are trivially done, so suppose that $G$ is an Ore composition of two $k$-Ore graphs $G_1$ and $G_2$ with overlap vertices $\{a,b\}$. We choose this composition to minimize $|V(G_1)|$.  Note that $D$ lies entirely on the edge-side or the split-side of this composition.  If $V(D)\subseteq V(G_1)$ then by Lemma \ref{lem:kOreAwayFromVertex} there is a diamond or an emerald in $G_2$ not containing the vertex $\underline{ab}\in V(G_2)$.  This is also a diamond or an emerald of $G$ and it is necessarily disjoint from $D$.

Therefore, we may assume that $D$ lies on the split-side.  We examine two cases based on if $V(D)$ contains one of the overlap vertices $\{a,b\}$ or not.  First, suppose that $V(D)$ contains neither $a$ nor $b$.  Then if $G_1=K_k$, then $G_1$ is a diamond that is disjoint from $D$.  Otherwise, $G_1$ is a composition of two $k$-Ore graphs $H_1$ and $H_2$ with overlap vertices $\{x,y\}$.  If the edge $ab\in E(G_1)$ is in $E(H_2)$ then there is a decomposition of $G$ with $H_1$ as the edge-side, which contradicts the minimality of $G_1$.
Thus, $ab\in E(H_1)$ and by Lemma \ref{lem:kOreAwayFromVertex} there is a diamond or an emerald in $H_2$ not containing $\underline{xy}\in V(H_2)$.  Note that this does not contain $a$ or $b$, so is also a diamond or emerald of $G$ which is disjoint from $D$.

Now we suppose that $V(D)$ and $\{a,b\}$ are not disjoint.  Because $ab\notin E(G)$, $|V(D)\cap\{a,b\}|=1$ and without loss of generality, we assume that $a\in V(D)$. If $G_2\neq K_k$ then by induction, there is a diamond or an emerald in $G_2$ disjoint from $D$.  This is also disjoint from $D$ in the graph $G$, so we may assume that $G_2=K_k$.  Because $\deg_{G_2}(\underline{ab})=k-1$, it follows that $b\in V(G)$ has exactly one neighbor on the split-side $G_2$.  By Lemma \ref{lem:kOreAwayFromVertex}, there is a diamond or emerald $D'$ in $G_1$ disjoint from $a$.  If $D'$ is a diamond, then it is also a diamond of $G$ that is disjoint from $D$ because $b\in V(D')$ implies that $b$ is an endpoint of $D'$, since $ab\in E(G_1)$.  If $D'$ is an emerald that does not contain $b$, then it is an emerald of $G$ that is disjoint from $D$.  If $D'$ is an emerald and $b\in V(D')$ then $\deg_{G_1}(b)=k-1$.  However, in $G$, $b$ is no longer adjacent to $a$, and has exactly one neighbor on the split-side $G_2$.  Therefore $\deg_G(b)=k-1$ as well and $D'$ is also an emerald of $G$ that is disjoint from $D$.
\end{proof}