Back to Search
Start Over
Edge Lower Bounds for List Critical Graphs, via Discharging
- Source :
- Combinatorica. Vol. 38(5), October 2018, pp. 1045-1065
- Publication Year :
- 2016
-
Abstract
- A graph $G$ is $k$-critical if $G$ is not $(k-1)$-colorable, but every proper subgraph of $G$ is $(k-1)$-colorable. A graph $G$ is $k$-choosable if $G$ has an $L$-coloring from every list assignment $L$ with $|L(v)|=k$ for all $v$, and 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. The problem of bounding (from below) the number of edges in a $k$-critical graph has been widely studied, starting with work of Gallai and culminating with the seminal results of Kostochka and Yancey, who essentially solved the problem. In this paper, we improve the best lower bound on the number of edges in a $k$-list-critical graph. Our proof uses the discharging method, which makes it simpler and more modular than previous work in this area.<br />Comment: 17 pages, 2 figures
- Subjects :
- Mathematics - Combinatorics
05C15
Subjects
Details
- Database :
- arXiv
- Journal :
- Combinatorica. Vol. 38(5), October 2018, pp. 1045-1065
- Publication Type :
- Report
- Accession number :
- edsarx.1602.02589
- Document Type :
- Working Paper