Department of
Applied
Mathematics

Coloring Graphs via VC_dimension

Stephan Thomasse

Abstract

We provide an upper bound on the chromatic number of graphs only depending of its fractional domination and a new complexity invariant for graphs called "paired VC dimension".

As a corollary, we directly obtain that for instance a graph G without Petersen subgraph and minimum degree n/10000 has bounded chromatic number.

We also characterize the graphs H such that H-free graphs with linear degree have bounded chromatic number.

This is joint work with T. Luczak.