\mychapter{Graph definitions and preliminaries}

\section{Definitions}

We begin with some graph notation that is frequently used in this work and then some preliminary lemmas which will be used in Chapter 6 during discharging.
In this work, we focus on $k$-critical graphs, a special type of graph with chromatic number $k$.
Recall the following definitions of the chromatic number and $k$-critical graphs.
A \emph{proper $k$-vertex-coloring}, or simply \emph{proper $k$-coloring} is a labelling such that adjacent vertices of $G$ receive different labels.
The \emph{chromatic number} of a graph $G$ is the smallest $k$ for which $G$ is properly $k$-colorable.
A \emph{$k$-critical graph} is a graph $G$ with chromatic number $k$ but for any $e\in E(G)$, the graph $G-e$ is properly $(k-1)$-colorable.

There are a few other definitions for graphs that we use frequently throughout this work which we make note of below.  Definitions not specifically stated in this work can be found in \cite{G88}.

For a graph $G$ we say that two subgraphs $H_1,H_2$ are \emph{incident} if $V(H_1)\cap V(H_2)\neq\emptyset$, we say that an edge $e$ is \emph{incident} to a vertex $x$ if $x$ is one of the endpoints of the edge, and we say that an edge $e$ is incident to an edge $f$ if $x\in V(G)$ is an endpoint of both edges.

The \emph{neighborhood}, $N_G(x)$, of a vertex $x\in V(G)$ is the set of all adjacent vertices.  The \emph{closed neighborhood}, $N_G[x]$, is the set $N_G(x)\cup\{x\}$.

For a graph $G$ with two vertices $x,y$ we define the graph $G/\underline{xy}$ to be the graph obtained from $G$ by identifying the vertices $x$ and $y$.  That is, $V(G/\underline{xy}):=(V(G)\cup\{\underline{xy}\})-\{x,y\}$ and the new vertex $\underline{xy}$ is adjacent to each vertex in $N_G(x)\cup N_G(y)$.


\section{Almost-bipartite subgraphs in a $k$-critical graph}

We begin this work on $k$-critical graphs by examining edge bounds of an almost-bipartite subgraph of a $k$-critical graph $G$.
By \emph{almost-bipartite} subgraph, we are referring to an induced subgraph on disjoint sets $A,B\subseteq V(G)$ such that $A$ is an independent set.
Because we only specify that $A$ is independent, the induced subgraph $G[A\cup B]$ is not necessarily bipartite.
In proving these results, we consider putting an orientation on edges of $G$ to create a digraph $D$.
On this digraph, we will make a list-coloring argument to achieve bounds on the number of edges in an almost-bipartite subgraph.

\begin{definition}
For a graph $G$ with disjoint vertex subsets $A,B$, we define $G(A,B)$ to be the bipartite graph obtained from $G[A\cup B]$ by removing all edges from $G[B]$ and $G[A]$.
We define $e_G(A,B)$ to be the number of edges in $G(A,B)$.
\end{definition}

For a graph (or digraph) $G$, a \emph{list} $L$ is a mapping which assigns to each $v\in V(G)$ a set of available colors for $v$.
Let $L(v)$ be a set of available colors for each $v\in V(G)$.
We say that $G$ is \emph{$L$-colorable} if there is a proper coloring $\phi$ of $G$ such that $\phi(v)\in L(v)$ for all $v$.
%if I want to use f-choosable language, then we can look at pg 410 of West

In \cite{KY2014}, the authors prove (Lemmas 8 and 9) the following statement, where $\deg_D^+(v)$ is the out-degree of $v$ in the digraph $D$.
\begin{lemma}\label{lem:Lcolorable}
Suppose that $A$ is an independent set in a graph $G$ and $B=V(G)-A$.  Let $D$ be the digraph obtained from $G$ by replacing each edge in $G[B]$ by a pair of opposite arcs and replacing each edge connecting $A$ with $B$ by an arc with arbitrary orientation.
If $L$ is a list such that
\[|L(v)|\geq1+\deg_D^+(v)\textrm{ for all }v\in V(D)\]
then $D$ is $L$-colorable.
\end{lemma}

The following lemma is a specific case of another result (Corollary 11) in \cite{KY2014}.
\begin{lemma}
Let $G$ be a $k$-critical graph with disjoint vertex subsets $A,B$ such that
\begin{enumerate}
\item $A$ is independent,
\item $\deg_G(a)=k-1$ for each $a\in A$, and
\item $\deg_G(b)=k$ for each $b\in B$.
\end{enumerate}
Then $e_G(A,B)\leq2|A|+2|B|$.
\end{lemma}
%\begin{proof}
%When $|A|+|B|<3$, one can check that $e_G(A,B)\leq2(|A|+|B|)$ regardless of any vertex degree, independence, or $k$-criticality of $G$.
%For $|A|+|B|\geq3$ the proof follows \cite{KY2014} exactly and we get $e_G(A,B)\leq2(|A|+|B|)-4\leq2(|A|+|B|)$.
%\end{proof}


We will need to prove similar lemmas where the vertices $b\in B$ all have degree $k+1$, or have degree $d$ with $k\leq d\leq k+1$.
\begin{lemma}\label{lem:eMQ}
Let $G$ be a $k$-critical graph with disjoint vertex subsets $A,B$ such that
\begin{enumerate}
\item $A$ is independent,
\item $\deg_G(a)=k-1$ for each $a\in A$,
\item and $\deg_G(b)=k+1$ for each $b\in B$.
\end{enumerate}
Then $e_G(A,B)\leq3(|A|+|B|)$.
\end{lemma}

\begin{proof}
Suppose that the hypotheses of the lemma hold.
If $A$ or $B$ are empty then $e_G(A,B)\leq3(|A|+|B|)$ is trivial, so we may assume that they are not empty.
Let $G'=G[A\cup B]$ and let $G''=G(A,B)$.
We claim that $\delta(G'')\leq3$.
Suppose, for sake of contradiction, that $\delta(G'')\geq4$.

From $G''$ we construct a new graph $H$ be splitting each vertex $b\in B$ into $\lceil d_{G''}(b)/4\rceil$ vertices of degree at most 4.
Let $B''$ be the partite set obtained from $B$ in this manner.
Then $H$ is a bipartite graph, $\deg_H(a)\geq4$ for each $a\in A$, and $\deg_H(b)\leq4$ for each $b\in B''$.
Hall's Theorem (\cite{H35}) gives a matching $M\subseteq E(H)$ that covers $A$.
Because each edge in $H$ corresponds to an edge in $G''=G(A,B)$, we will also say that $M\subseteq E(G'')$

Now we construct a digraph $D$ from $G'$ by replacing each edge in $G[B]$ by a pair of opposite arcs, orienting all edges of $M\subseteq E(G'')$ toward $A$, and orienting all remaining edges in $E(G'')$ towards $B$.
Because $G$ is $k$-critical, we can properly $(k-1)$-color $G-\{A\cup B\}$ with $\phi$ using color set $C$.  For each $v\in A\cup B$, we let 
\[L(v):=C-\bigcup_{\stackrel{x\in V(G)-(A\cup B)}{xv\in E(G)}} \phi(x).\]
Note that for any $v\in (A\cup B)$ we get $|L(v)|\geq(k-1)-\deg_G(v)+\deg_{G'}(v)$.
Therefore for $a\in A$ and $b\in B$, we have $|L(a)|\geq\deg_{G'}(a)$ and $|L(b)|\geq\deg_{G'}(b)-2$.
It follows that $\deg_D^+(a)=\deg_{G'}(a)-1\leq|L(a)|-1$.
Further, because each $b\in B$ has at most  $\lceil\frac{1}{4}\deg_{G''}(b)\rceil$ incident arcs which are oriented towards $A$ and because each $b$ has at least 4 neighbors in $A$ it follows that
\[\deg_D^+(b)\leq\deg_{G'}(b)-\left\lfloor\frac{3}{4}\deg_{G''}(b)\right\rfloor\leq(|L(b)|+2)-3=|L(b)|-1.\]
By Lemma \ref{lem:Lcolorable} $D$ is $L$-colorable.  But this implies that $\phi$ can be extended to properly $(k-1)$-color $G$, which is a contradiction.
Therefore, we have shown that $\delta(G'')\leq3$.

We now prove by induction on $(|A|+|B|)$ that $e_G(A,B)\leq3(|A|+|B|)$.
This is trivial for $|A|+|B|=2$, which is the base case.
Now suppose that $|A|+|B|=\ell$ and that the lemma holds for $|A|+|B|<\ell$.
Because $\delta(G'')\leq3$, there is a vertex $x$ with $\deg_{G''}(x)=d\leq3$; without loss of generality, suppose that $x\in A$.
By the inductive hypothesis $e_G(A-\{x\},B)\leq 3(|A|+|B|-1)$.
Therefore $e_G(A,B)\leq3(|A|+|B|)-3+d\leq3(|A|+|B|).$
\end{proof}



\begin{lemma}\label{lem:eLPQ}
Let $G$ be a $k$-critical graph with disjoint vertex subsets $A,B_0,B_1$ and let $B:=B_0\cup B_1$.
If
\begin{enumerate}
\item $A$ is independent,
\item $\deg_G(a)=k-1$ for each $a\in A$,
\item and $\deg_G(b)=k+i$ for each $b\in B_i$ with $0\leq i\leq1$.
\end{enumerate}
Then $e_G(A,B)\leq2|A|+2|B_0|+4|B_1|$.
\end{lemma}

\begin{proof}
Suppose that the hypotheses of the lemma hold.
If $A$ or $B$ are empty then $e_G(A,B)\leq2|A|+2|B_0|+4|B_1|$ is trivial, so we may assume that they are not empty.
Let $G'=G[A\cup B]$ and let $G''=G(A,B)$.
We claim that either there is some $a\in A$ with $\deg_{G''}(a)\leq2$ or some $b_i\in B_i$ with $\deg_{G''}(b_i)\leq2+2i$ for $0\leq i\leq1$.
Suppose, for sake of contradiction, that $\deg_{G''}(a)\geq3$ for all $a\in A$ and $\deg_{G''}(b_i)\geq3+2i$ for all $b_i\in B_i$ with $0\leq i\leq1$.

From $G''$ we construct a new graph $H$ be splitting each vertex $b\in B$ into $\lceil d_{G''}(b)/3\rceil$ vertices of degree at most 3.
Let $B''$ be the partite set obtained from $B$ in this manner.
Then $H$ is a bipartite graph, $\deg_H(a)\geq3$ for each $a\in A$, and $\deg_H(b)\leq3$ for each $b\in B''$.
Hall's Theorem (\cite{H35}) gives a matching $M\subseteq E(H)$ that covers $A$.
Because each edge in $H$ corresponds to an edge in $G''=G(A,B)$, we will also say that $M\subseteq E(G'')$

Now we construct a digraph $D$ from $G'$ by replacing each edge in $G[B]$ by a pair of opposite arcs, orienting all edges of $M\subseteq E(G'')$ toward $A$, and orienting all remaining edges in $E(G'')$ towards $B$.
Because $G$ is $k$-critical, we can properly $(k-1)$-color $G-\{A\cup B\}$ with $\phi$ using color set $C$.  For each $v\in A\cup B$, we let 
\[L(v):=C-\bigcup_{\stackrel{x\in V(G)-(A\cup B)}{xv\in E(G)}} \phi(x).\]
Note that for any $v\in (A\cup B)$ we get $|L(v)|\geq(k-1)-\deg_G(v)+\deg_{G'}(v)$.
Therefore for $a\in A$ and $b_i\in B_i$ we have $|L(a)|\geq\deg_{G'}(a)$ and $|L(b_i)|\geq\deg_{G'}(b_i)-1-i$.
It follows that $\deg_D^+(a)=\deg_{G'}(a)-1\leq|L(a)|-1$.
Further, because each $b_i\in B_i$ has at most  $\lceil\frac{1}{3}\deg_{G''}(b_i)\rceil$ incident arcs which are oriented towards $A$ and because each $b_i$ has at least $3+2i$ neighbors in $A$ it follows that
\[\deg_D^+(b_i)\leq\deg_{G'}(b_i)-\left\lfloor\frac{2}{3}\deg_{G''}(b_i)\right\rfloor\leq(|L(b_i)|+1+i)-\left\lfloor\frac{6+4i}{3}\right\rfloor=|L(b_i)|-1.\]
By Lemma \ref{lem:Lcolorable} $D$ is $L$-colorable.  But this implies that $\phi$ can be extended to properly $(k-1)$-color $G$, which is a contradiction.
Therefore, we have shown that there is either some $a\in A$ with $\deg_{G''}(a)\leq2$ or some $b_i\in B_i$ with $\deg_{G''}(b_i)\leq2+2i$ for $0\leq i\leq1$.

We now prove by induction on $(|A|+|B|)$ that $e_G(A,B)\leq2|A|+2|B_0|+4|B_1|$.
This is trivial for $|A|+|B|=2$, which is the base case.
Now suppose that $|A|+|B|=\ell$ and that the lemma holds for $|A|+|B|<\ell$.
Suppose that there is some $a\in A$ with $\deg_{G''}(a)=d\leq2$.
By the inductive hypothesis $e_G(A-\{a\},B)\leq2(|A|-1)+2|B_0|+4|B_1|$.
Therefore $e_G(A,B)\leq2(|A|-1)+2|B_0|+4|B_1|+d\leq2|A|+2|B_0|+4|B_1|.$

Now suppose instead that there is some $b_i\in B_i$ with $\deg_{G''}(b_i)=d\leq2+2i$.
By the inductive hypothesis and assumption on degree of $b_i$ it follows that
\[e_G(A,B)\leq\left(2|A|+2|B_0|+4|B_1|-2-2i\right)+d\leq2|A|+2|B_0|+4|B_1|.\]
\end{proof}

\section{Further edge bound on $k$-critical graphs}


The following lemma, used in the second stage of discharging in Chapter 6, is a restatement in terms of $k$-critical graphs of a theorem from Kierstead and Rabern (Theorem 4.5) \cite{KR2014}.  Let $\text{mic}(G)$ be the maximum of $\sum_{v\in I}\deg_G(v)$ over all independent vertex subsets $I$ of $G$.
\begin{lemma}\label{lem:KR}
Given a $k$-critical graph $G$ with at least one vertex of degree $k-1$,
\[2|E(G)|\geq (k-2)|V(G)|+\text{mic}(G)+1.\]
\end{lemma}
%Do I need to explain why the other case isn't possible? !!!
In this work, we omit the $+1$ because the other two terms scale with $|V(G)|$.
