Alexandr V. Kostochka: A trick for proving properties of (a,b)-sparse graphs

A graph G is (a,b)-sparse if for every non-empty subset A of V(G), |E(G[A])| < a|A|+b. For example, by a Nash-Williams' Theorem, a graph has edge-arboricity at most 2 exactly when it is (2,-1)-sparse. Suppose that we want to prove that every (a,b)-sparse graph has a hereditary property P (for example, has a special vertex partition). Then it would be good to know that for every proper "large" subset A of the vertex set of a minimum counter-example G, we have the stronger inequality |E(G[A])| < a|A|+b-1.

We show how this simple idea helps to prove that every 4-color-critical n-vertex graph has at least (5n-2)/3 edges, which is a partial case of Gallai's Conjecture from 1963 (jont result with M. Yancey). We also show some applications of this to 3-coloring of planar graphs (joint with O. Borodin, B. Lidick\' y and M. Yancey).