The chromatic number of a graph is the minimum number of colours one needs to colour its vertices so that the endpoints of every edge receive distinct colours. This metric, introduced nearly two centuries ago, has since played a central role in graph theory and has found numerous practical applications.
A natural question in structural graph theory is how the chromatic number constrains the structure of graphs. One prominent example is the Gyárfás-Sumner conjecture, which aims to characterize the local structure of graphs with arbitrarily large chromatic number. Although this question may sound like yet another structural graph theorist’s favourite refrain (« how does metric interact with graph structure? ») we will explain why it is genuinely well motivated and how one is naturally led to the Gyárfás-Sumner conjecture.
We then show how similar lines of reasoning lead to similarly flavoured conjectures for other combinatorial objects, in particular directed graphs. We conclude by presenting recent advances towards this directed analogue of the Gyárfás-Sumner conjecture.
This talk features joint works with Pierre Aboulker, Pierre Charbit, Luis Kuffner, Rafael Steiner and Stephan Thomassé.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne