Graphs and Matroids Seminar - Alvaro Carbonero Gonzales

Title: An into introduction to the chromatic number of digraph

Abstract: A proper $k$-coloring of a digraph $D$ is a coloring of the vertices such that every color class is acyclic, and the dichromatic number of a digraph $D$ is the minimum number $k$ such that there is a proper $k$-coloring of $D$. Many questions about the chromatic number can be asked about the dichromatic number, but as one will quickly observe, unsuspected complications arise when dealing with digraphs. In this presentation, we will see how famous conjectures about the chromatic number, like the Gyarfas-Sumner conjecture, translate to questions about the dichromatic number, and we will see the progress towards answering these questions. In addition to covering the known results, we will also see how many common arguments, like the Gyarfas' path argument, do not work in the directed setting, making seemingly easy questions in reality surprisingly hard.