A trick for proving properties of (a,b)-sparse graphs

Graphs, Hypergraphs, and Computing

11 March 14:00 - 15:00

Alexandr V. Kostochka - University of Illinois at Urbana-Champaign

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).
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to