Discrete Math Seminar: The heroes of digraphs: coloring digraphs with forbidden induced subgraphs
Author: Lona | Image: Lona
Speaker: Alvaro Carbonero Gonzales, University of WaterlooAbstract:The chromatic number is one of the most studied graph invariants in graph theory. $\chi$-boundedness, for instance, studies the induced subgraphs present in graphs with large chromatic number and small clique number. Neumann-Lara introduced an analog directed version of this graph invariant: the dichromatic number of digraphs. In this talk, we start by seeing some analogous results from the field of $\chi$-boundedness in this context. In particular, we will talk about heroes. A hero $H$ in a class of digraphs $\mathcal{C}$ is a digraph with the property that $H$-free digraphs $D\in \mathcal{C}$ have bounded dichromatic number. After going over the known results regarding heroes, we present a new result (obtained in collaboration with Hidde Koerts, Benjamin Moore, and Sophie Spirkl) which almost fully characterizes heroes in ${rK1+\vec{P_3}}$-free digraphs.