Improved lower bounds on the number of edges in list critical and online list critical graphs

preprint2015arXivOpen access

Abstract

We prove that every kk-list-critical graph (k≥7k \ge 7) on n≥k+2n \ge k+2 vertices has at least 12(k−1+k−3(k−c)(k−1)+k−3)n\frac12 \left(k-1 + \frac{k-3}{(k-c)(k-1) + k-3}\right)n edges where c=(k−3)(12−1(k−1)(k−2))c = (k-3)\left(\frac12 - \frac{1}{(k-1)(k-2)}\right). This improves the bound established by Kostochka and Stiebitz. The same bound holds for online kk-list-critical graphs, improving the bound established by Riasat and Schauz. Both bounds follow from a more general result stating that either a graph has many edges or it has an Alon-Tarsi orientable induced subgraph satisfying a certain degree condition.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.