Dear all,

There will be a noon seminar this Thursday, 16 November, given by Guillaume Aubian.
Please find the talk details below.

Best regards,
Misha Tyomkyn.
Towards a directed analogue of Gyárfás-Sumner conjecture!
Guillaume Aubian
Charles University
November 16, 2023, 12:20 in S6

Abstract
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.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz
To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz