Working Seminar on Formal Models, Discrete Structures, and Algorithms

Coloring vertex-minor-free graphs with no short cycle

James Davies (University of Warwick)

When: Monday March 19, 2 pm

Where: room C417

Abstract

Geelen conjectured that every proper vertex-minor closed class of graphs is chi-bounded, i.e., for every graph G within the class, the chromatic number of G is bounded by a function of its clique number.

Motivated by this conjecture, we show that for every proper vertex-minor closed class, there exists K such that every graph G within the class with girth at least 10 has chromatic number at most K.