14:00
15:00

** Une famille de graphe sans triangles avec certaines propriétés **

/Exposé /Talk/

We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every non-trivial graph 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 Trotignon. The class is the hereditary closure of a family of triangle-free twincut graphs $G_1, G_2, \ldots$ such that $G_k$ has chromatic number $k$. We study various properties of these graphs highlighting their strikingly low structural complexity. Joint work with Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé and Nicolas Trotignon.

[Romain Bourneuf ] (LaBRI )
http://perso.ens-lyon.fr/romain.bourneuf/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI/178