On the chromatic number of digraphs
Ararat Harutyunyan

01 June 2012, 10h30 - 01 June 2012, 11h30 Salle/Bat : 455/PCRI-N
Contact :

Activités de recherche :

Résumé :

We will review some results which provide evidence that partitioning the vertex set of a digraph into the smallest number of acyclic sets is the natural extension of the notion of the chromatic number of (undirected) graphs. We will also present some recently obtained results in this area. In particular, we will show analogs of Brooks' Theorem and Gallai's Theorem for digraphs, and explore the complexity of some algorithmic problems.
Then we will discuss some extremal results as well as problems on planar digraphs.