Séminaire Equipe RORSS

Analogue of Gyarfas-Sumner conjecture for oriented graphs


12/14/2021
Speaker(s) : Pierre Aboulker
Gyarfas-Sumner Conjecture asserts that for every integer k and every forest T, the class of graphs with no clique on k vertices nor induced subgraph isomorphic to T have bounded chromatic number. We will investigate an analogue of this conjecture for oriented graphs. This is a joint works with Guillaume Aubian, Pierre Charbit and Reza Naserasr