Pierre Aboulker - Clique number of tournaments

Speaker: Zoltan Szigeti

Title:  Evolution of arborescence packing

Room: A707

Date: 03/11/2025 14:00

Abstract:

The dichromatic number of a digraph is the minimum integer k such that the vertex set of D can be partitioned into k acyclic subdigraphs. It is easy to see that the chromatic number of a graph G is equivalent to the dichromatic number of the digraph obtained from G by replacing each edge with a digon (two anti-parallel arcs). Based on this simple observation, many theorems concerning the chromatic number of undirected graphs have been generalized to digraphs via the dichromatic number. However, no concept analogous to the clique number for digraphs has been available. The purpose of this presentation is to explore such a concept and its relationship with the dichromatic number, mirroring the relationship between the clique number and the chromatic number in undirected graphs. We will focus, in particular, on studying the notion of χ-boundedness.