\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.37}{23(3)}{2016}
\usepackage{amsmath, amsthm, amssymb}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prob}[thm]{Problem}

\newtheorem*{KernelLemma}{Kernel Lemma}
\newtheorem*{KernelMagic}{Kernel Magic}
\newtheorem*{TheLemma}{Lemma}
\newtheorem*{MainTheorem}{Main Theorem}
\newtheorem*{TheConjecture}{Conjecture}
\theoremstyle{definition}
\newtheorem*{TheDefinition}{Definition}
\newtheorem{defn}{Definition}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\newtheorem*{problem}{Problem}
\newtheorem{example}{Example}
\newtheorem*{question}{Question}
\newtheorem*{observation}{Observation}

\newcommand{\fancy}[1]{\mathcal{#1}}
\newcommand{\C}[1]{\fancy{C}_{#1}}
\newcommand{\IN}{\mathbb{N}}
\newcommand{\IR}{\mathbb{R}}
\newcommand{\G}{\fancy{G}}
\newcommand{\CC}{\fancy{C}}
\newcommand{\D}{\fancy{D}}
\newcommand{\T}{\fancy{T}}
\newcommand{\B}{\fancy{B}}
\renewcommand{\L}{\fancy{L}}
\newcommand{\HH}{\fancy{H}}

\newcommand{\inj}{\hookrightarrow}
\newcommand{\surj}{\twoheadrightarrow}

\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\setb}[3]{\left\{ #1 \in #2 : #3 \right\}}
\newcommand{\setbs}[2]{\left\{ #1 : #2 \right\}}
\newcommand{\card}[1]{\left|#1\right|}
\newcommand{\size}[1]{\left\Vert#1\right\Vert}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\func}[3]{#1\colon #2 \rightarrow #3}
\newcommand{\funcinj}[3]{#1\colon #2 \inj #3}
\newcommand{\funcsurj}[3]{#1\colon #2 \surj #3}
\newcommand{\irange}[1]{\left[#1\right]}
\newcommand{\join}[2]{#1 \mbox{\hspace{2 pt}$\ast$\hspace{2 pt}} #2}
\newcommand{\djunion}[2]{#1 \mbox{\hspace{2 pt}$+$\hspace{2 pt}} #2}
\newcommand{\parens}[1]{\left( #1 \right)}
\newcommand{\brackets}[1]{\left[ #1 \right]}
\newcommand{\DefinedAs}{\mathrel{\mathop:}=}

\newcommand{\mic}{\operatorname{mic}}
\newcommand{\AT}{\operatorname{AT}}
\newcommand{\col}{\operatorname{col}}
\newcommand{\ch}{\operatorname{ch}}
\newcommand{\type}{\operatorname{type}}
\newcommand{\nonsep}{\bar{S}}

\def\adj{\leftrightarrow}
\def\nonadj{\not\!\leftrightarrow}

\def\D{\fancy{D}}
\def\C{\fancy{C}}
\def\A{\fancy{A}}
\def\chil{{\chi_\ell}}
\def\chiol{\chi_{\rm{OL}}}

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\title{\bf A better lower bound on average degree of 4-list-critical graphs}
\author{Landon Rabern\\
\small LBD Data\\[-0.8ex]
\small 314 Euclid Ave.\\[-0.8ex] 
\small Mount Gretna, Pennsylvania, USA\\
\small\tt landon@lbd-data.com}


\date{\dateline{Feb 27, 2016}{Aug 10, 2016}{Aug 19, 2016}\\
\small Mathematics Subject Classifications: 05C15}

\begin{document}
\maketitle
\begin{abstract}
		This short note proves that every non-complete $k$-list-critical graph has average degree at least $k-1 + \frac{k-3}{k^2-2k+2}$.  This improves the best known bound for $k = 4,5,6$.
		The same bound holds for online $k$-list-critical graphs.
\end{abstract}

\section{Introduction}
A graph $G$ is \emph{$k$-list-critical} if $G$ is not $(k-1)$-choosable, but every
proper subgraph of $G$ is $(k-1)$-choosable.  For further definitions and notation, see \cite{OreVizing, DischargingLowerBound}. 
Table \ref{TheTable} shows some history of lower bounds on the average degree of $k$-list-critical graphs.

\begin{MainTheorem}
	Every non-complete $k$-list-critical graph has average degree at least \[k-1 + \frac{k-3}{k^2-2k+2}.\]
\end{MainTheorem}

Main Theorem gives a lower bound of $3 + \frac{1}{10}$ for $4$-list-critical graphs. This is the first improvement over Gallai's bound of $3 + \frac{1}{13}$. 
The same proof shows that Main Theorem holds for online $k$-list-critical graphs as well.  Our primary tool is a lemma proved with Kierstead \cite{KernelMagic} 
that generalizes a kernel technique of Kostochka and Yancey \cite{kostochkayancey2012ore}.

\begin{TheDefinition} The \emph{maximum independent cover number }of a graph $G$
	is the maximum $\mic(G)$ of $\size{I, V(G) \setminus I}$ over all independent sets $I$
	of $G$. 
\end{TheDefinition}

\begin{KernelMagic}[Kierstead and R. \cite{KernelMagic}]\label{ConsantListMicStrength} 
	Every $k$-list-critical graph $G$ satisfies
	\[2\size{G} \ge (k-2)\card{G} + \mic(G) + 1.\]
\end{KernelMagic}
The previous best bounds in Table \ref{TheTable} for $k$-list-critical graphs hold for k-Alon-Tarsi-critical graphs as well. Since Kernel Magic relies on the Kernel Lemma, 
our proof does not work for k-Alon-Tarsi-critical graphs.  Any improvement over Gallai's bound of $3 + \frac{1}{13}$ for 4-Alon-Tarsi-critical graphs would be interesting.


\begin{table}
	\begin{center}
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
			\hline
			&\multicolumn{4}{ |c| }{$k$-Critical
				$G$}&\multicolumn{4}{|c|}{$k$-List Critical $G$}\\
			\hline
			& Gallai \cite{gallai1963kritische}
			& Kriv \cite{krivelevich1997minimal}
			& KS \cite{kostochkastiebitzedgesincriticalgraph}
			& KY \cite{kostochkayancey2012ore}
			& KS \cite{kostochkastiebitzedgesincriticalgraph} 
			& KR \cite{OreVizing}
			& CR \cite{DischargingLowerBound}
			& Here \\
			$k$ & $d(G) \ge$ & $d(G) \ge$ & $d(G) \ge$ & $d(G) \ge$ & $d(G) \ge$ & $d(G) \ge$ & $d(G) \ge$ & $d(G) \ge$\\
			\hline 
			4 & 3.0769 &3.1429&---&3.3333& --- & --- & --- & \bf{3.1000}\\
			5 & 4.0909 &4.1429&---&4.5000& --- & 4.0984 & 4.1000 & \bf{4.1176}\\
			6 & 5.0909 &5.1304&5.0976&5.6000& --- & 5.1053 & 5.1076 & \bf{5.1153}\\
			7 & 6.0870 &6.1176&6.0990&6.6667& --- & 6.1149 & \bf{6.1192} & 6.1081\\
			8 & 7.0820 &7.1064&7.0980&7.7143& --- & 7.1128 & \bf{7.1167} & 7.1000\\
			9 & 8.0769 &8.0968&8.0959&8.7500& 8.0838 & 8.1094 & \bf{8.1130} & 8.0923\\
			10 & 9.0722 &9.0886&9.0932&9.7778& 9.0793 & 9.1055 & \bf{9.1088} & 9.0853\\
			15 & 14.0541 &14.0618&14.0785&14.8571& 14.0610 & 14.0864 & \bf{14.0884} & 14.0609\\
			20 & 19.0428 &19.0474&19.0666&19.8947& 19.0490 & 19.0719 & \bf{19.0733} & 19.0469 \\
			\hline
		\end{tabular}
	\end{center}
	\caption{History of lower bounds on the average degree $d(G)$ of $k$-critical and $k$-list-critical graphs $G$.}
	\label{TheTable}
\end{table}

\section{The Proof}
The connected graphs in which each block is a complete graph
or an odd cycle are called \emph{Gallai trees}.  Gallai \cite{gallai1963kritische} proved that in a $k$-critical graph, the vertices of degree $k-1$ induce a disjoint union of Gallai trees.  
The same is true for $k$-list-critical graphs \cite{borodin1977criterion, erdos1979choosability}.  For a graph $T$ and $k \in \IN$, let $\beta_k(T)$ be the independence number of the subgraph of $T$ 
induced on the vertices of degree $k-1$ in $T$.  When $k$ is defined in the context, put $\beta(T) 
\DefinedAs \beta_k(T)$.  

\begin{lem}\label{BetaaaBound}
	If $k \ge 4$ and $T \ne K_k$ is a Gallai tree with maximum degree at most $k-1$, then
	\[2||T|| \le (k-2)|T| + 2\beta(T).\]
\end{lem}
\begin{proof}
	Suppose the lemma is false and choose a counterexample $T$ minimizing $\card{T}$.  Plainly, $T$ has more than one block.  Let $A$ be an endblock of $T$ and let $x$ be the unique cutvertex of $T$ with $x \in V(A)$.
	Consider $T' \DefinedAs T - (V(A)\setminus\set{x})$.  By minimality of $\card{T}$,
	\begin{equation*}
		2\size{T} - 2\size{A} \le (k-2)(\card{T} + 1 - \card{A}) + 2\beta(T').
	\end{equation*}
		Since $T$ is a counterexample, $2\size{A} > (k-2)(\card{A} - 1)$.  So, if $k > 4$, then $A = K_{k-1}$ and if $k=4$, then $A$ is an odd cycle.  In both cases, $d_T(x) = k-1$.
	Consider $T^* \DefinedAs T - V(A)$.  By minimality of $\card{T}$,
	\begin{equation*}
	2\size{T} - 2\size{A} - 2 \le (k-2)(\card{T} - \card{A}) + 2\beta(T^*).
	\end{equation*}
	Since $T$ is a counterexample, $2\size{A} + 2 > (k-2)\card{A} + 2(\beta(T) - \beta(T^*))$.  In $T^*$, all of $x$'s neighbors have degree at most $k-2$.
	But $d_T(x) = k-1$, so some vertex in $\set{x} \cup N(x)$ is in a maximum independent set of degree $k-1$ vertices in $T$.  Hence $\beta(T^*) \le \beta(T) - 1$, which gives
	\begin{equation*}
	 2\size{A} > (k-2)\card{A},
	\end{equation*}
	a contradiction since $k \ge 4$.
\end{proof}

\begin{proof}[Proof of Main Theorem]
Let $G \ne K_k$ be a $k$-list-critical graph.  The theorem is trivially true if $k \le 3$, so suppose $k \ge 4$. Let $\L \subseteq V(G)$ be the vertices with degree $k-1$ and let $\HH = V(G) \setminus \L$.  Put $\size{\L} \DefinedAs \size{G[\L]}$ and $\size{\HH} \DefinedAs \size{G[\HH]}$.  
By Lemma \ref{BetaaaBound},
	\begin{equation*}
	2\size{\L} \le (k-2)|\L| + 2\beta(\L)
	\end{equation*}
	Hence,
	\begin{align*}
	2\size{G} &= 2\size{\HH} + 2\size{\HH, \L} + 2\size{\L}\\
	&= 2\size{\HH} + 2((k-1)\card{\L} - 2\size{\L}) + 2\size{\L}\\
	&= 2\size{\HH} + 2(k-1)\card{\L} - 2\size{\L}\\
	&\ge 2\size{\HH} + k\card{\L} - 2\beta(\L),\\
	\end{align*}
	which is
	\begin{equation}
	\beta(\L) \ge \size{\HH} + \frac{k}{2}\card{\L} - \size{G}.
	\label{BetaBound}
	\end{equation}
	Let $M$ be the maximum of $\size{I, V(G) \setminus I}$ over all independent sets $I$ of $G$ with $I \subseteq \HH$.   Since the vertices in $\L$ with $k-1$ neighbors in $\L$ have no neighbors in $\HH$,
	
	\begin{equation*}
		\mic(G) \ge M + (k-1)\beta(\L).
	\end{equation*}
	Applying Kernel Magic and using (\ref{BetaBound}) gives
	\begin{align*}
	2\size{G} &\ge (k-2)\card{G} + M + (k-1)\beta(\L) + 1\\
	&\ge (k-2)\card{G} + M + (k-1)\parens{\size{\HH} + \frac{k}{2}\card{\L} - \size{G}} + 1\\
	&= (k-2)\card{G} + M + (k-1)\size{\HH} + \frac{k(k-1)}{2}\card{\L} - (k-1)\size{G} + 1.
	\end{align*}		
	Hence
	\begin{equation}
	(k+1)\size{G} \ge (k-2)\card{G} + M + (k-1)\size{\HH} + \frac{k(k-1)}{2}\card{\L} + 1
	\label{KPOBound}
	\end{equation}
	Let $\C$ be the components of $G[\HH]$.  Then $\alpha(C) \ge \frac{\card{C}}{\chi(C)}$ for all $C \in \C$.  Whence
	\begin{equation}
	  M + (k-1)\size{\HH} \ge \sum_{C \in \C} k\frac{\card{C}}{\chi(C)} + (k-1)\size{C}.
	  \label{Mbound}
	\end{equation}
	
	If $\L = \emptyset$, then $G$ has average degree at least $k \ge k-1 + \frac{k-3}{k^2-2k+2}$.  So, assume $\L \ne \emptyset$.  Then $G[\HH]$ is $(k-1)$-colorable by $k$-list-criticality of $G$. In particular, $\chi(C) \le k-1$ for every $C \in \C$.
	For every $C \in \C$,
	\begin{equation}
	 k\frac{\card{C}}{\chi(C)} + (k-1)\size{C} \ge \parens{k - \frac12}\card{C}.
	 \label{KFC}
	\end{equation}
	To see this, first suppose $C \in \C$ is not a tree. Then $\size{C} \ge \card{C}$ and hence $k\frac{\card{C}}{\chi(C)} + (k-1)\size{C} \ge k\frac{\card{C}}{k-1} + (k-1)\card{C} \ge (k - \frac12)\card{C}$.  If $C$ is a tree, then $\chi(C) \le 2$ and hence 
	$k\frac{\card{C}}{\chi(C)} + (k-1)\size{C} \ge k\frac{\card{C}}{2} + (k-1)(\card{C} - 1) \ge (k-\frac12)\card{C}$ unless $\card{C} = 1$.  This proves (\ref{KFC}) since the bound is trivially satisfied when $\card{C} = 1$.
	
	Now combining (\ref{KPOBound}), (\ref{Mbound}) and (\ref{KFC}) with the basic bound
	\begin{equation*}
	  \card{\L} \ge k\card{G} - 2\size{G},
	\end{equation*}	
	gives
	\begin{align*}
	(k+1)\size{G} &\ge (k-2)\card{G} + \parens{k - \frac12}\card{\HH} + \frac{k(k-1)}{2}\card{\L} + 1\\
	&= \parens{2k-\frac52}\card{G} + \frac{k^2 - 3k + 1}{2}\card{\L} + 1\\
	&\ge\parens{2k-\frac52}\card{G} + \frac{k^2 - 3k + 1}{2}\parens{k\card{G} - 2\size{G}} + 1.\\
	\end{align*}
	After some algebra, this becomes
	\begin{equation*}
		2\size{G} \ge \parens{k-1 + \frac{k-3}{k^2 -2k + 2}}\card{G} + \frac{2}{k^2 -2k + 2}.
	\end{equation*}
	That proves the theorem.
\end{proof}

The right side of equation (\ref{KFC}) in the above proof can be improved to $k\card{C}$ unless $C$ is a $K_2$ where both vertices have degree $k$ in $G$.  
If these $K_2$'s could be handled, the average degree bound would improve to $k-1 + \frac{k-3}{(k-1)^2}$.  

\begin{TheConjecture}
Every non-complete (online) $k$-list-critical graph has average degree at least \[k-1 + \frac{k-3}{(k-1)^2}.\]
\end{TheConjecture}

\begin{thebibliography}{99}

\bibitem{borodin1977criterion}
O.V. Borodin, \emph{{Criterion of chromaticity of a degree prescription}},
  Abstracts of IV All-Union Conf. on Th. Cybernetics, 1977, pp.~127--128.

\bibitem{DischargingLowerBound}
D.~Cranston and L.~Rabern, \emph{Edge lower bounds for list critical graphs,
  via discharging}, \arxiv{1602.02589} (2016).

\bibitem{erdos1979choosability}
P.~Erd\H{o}s, A.L. Rubin, and H.~Taylor, \emph{{Choosability in graphs}}, Proc.
  West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus
  Numerantium, vol.~26, 1979, pp.~125--157.

\bibitem{gallai1963kritische}
T.~Gallai, \emph{{Kritische Graphen I.}}, Publ. Math. Inst. Hungar. Acad. Sci
  \textbf{8} (1963), 165--192 (in German).

\bibitem{OreVizing}
H.A. Kierstead and L.~Rabern, \emph{Improved lower bounds on the number of
  edges in list critical and online list critical graphs}, \arxiv{1406.7355} (2014).

\bibitem{KernelMagic}
\bysame, \emph{{Extracting list colorings from large independent sets}},
  \arxiv{1512.08130} (2015).

\bibitem{kostochkastiebitzedgesincriticalgraph}
A.V. Kostochka and M.~Stiebitz, \emph{A new lower bound on the number of edges
  in colour-critical graphs and hypergraphs}, Journal of Combinatorial Theory,
  Series B \textbf{87} (2003), no.~2, 374--402.

\bibitem{kostochkayancey2012ore}
A.V. Kostochka and M.~Yancey, \emph{Ore's conjecture on color-critical graphs
  is almost true}, J. Combin. Theory Ser. B \textbf{109} (2014), 73--101.

\bibitem{krivelevich1997minimal}
M.~Krivelevich, \emph{On the minimal number of edges in color-critical graphs},
  Combinatorica \textbf{17} (1997), no.~3, 401--426.

\end{thebibliography}

\end{document} 
