Towards a directed analogue of Gyárfás-Sumner conjecture!

Guillaume Aubian

Charles University

November 16, 2023, 12:20 in S6


In 1982, Victor Neumann-Lara introduced the dichromatic number, a directed analogue of the chromatic number for directed graphs. Since then, this novel idea has been successfully used to extend results and conjectures on undirected graphs to the realm of directed graphs.

One of the most important conjecture in graph colouring is the Gyárfás-Sumner conjecture, which seeks to describe the induced subgraphs that must necessarily appear in graphs of sufficiently large chromatic number. However, this conjecture remains widely open. In 2019, Aboulker, Charbit and Naserasr described an analogue conjecture for the dichromatic number, based upon the concept of heroes, a notion initially introduced by Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott, Seymour and Thomassé.

In the pursuit of solving this problem, significant progress has been achieved, including the refutation of certain aspects of the original conjecture: we provide an overview of these advances.