A tamed family of triangle-free graphs with unbounded chromatic number

-
Nicolas Trotignon, CNRS and ENS de Lyon
Fine Hall 224

We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every graph on at least three vertices either contains a pair of non-adjacent twins or has an edgeless vertex cutset of size at most two. This answers in the negative a question of Chudnovsky, Penev, Scott and the speaker. These graphs are structurally simple in several ways, in particular regarding their twinwidth. Also, we show how to obtain such graphs with arbitrarily large odd girth. This is joint work with Édouard Bonnet, Romain Bourneuf, Julien Duron, Colin Geniet and Stéphan Thomassé.