Seminar

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

Program
Contact

Klas Markström

klas.markstrom@math.umu.se

Other
information

For practical matters at the Institute, send an e-mail to secretary@mittag-leffler.se