Some results on directed coloring

-- Thomas Bellitto (LIP6, Sorbonne University)

Time: 14:00 -- Location: LRI, 445

summary: Proper coloring of undirected graphs lies among the most studied problems in graph theory. It asks to color vertices while giving different colors to adjacent ones.
In 1982, Neumann-Lara introduced a generalization of this problem to directed graphs. When walking in an undirected graph, an undirected edge between two vertices \(u\) and \(v\) can be used both to go from \(u\) to \(v\) and from \(v\) to \(u\), while in a directed graph, an arc \(uv\) can only lead from \(u\) to \(v\). As such, undirected graphs can be seen as a special case of directed graphs where for every arc \(uv\), there also exists an arc \(vu\). Neumann-Lara's generalized coloring of directed graphs requires that there exists no monochromatic closed walk in the graph i.e. no walk that starts and ends on the same vertex and only uses vertices of the same color. Like in the undirected case, a pair of arcs \(uv\) and \(vu\) (such a pair is called a digon) enforce that \(u\) and \(v\) receive different colors since they form a closed walk. However, if there is no arc \(vu\), \(u\) and \(v\) may receive the same color even if there is an arc \(uv\), as long as there is no monochromatic walk from \(v\) to \(u\).
This definition has received evergrowing attention since its introduction, and generalizing the very rich chromatic graph theory to directed graphs raises a lot of interesting challenges. In this talk, I will give an overview of various works I did on this topic with several co-authors. I will mainly focus on the study of minimal graphs of given dichromatic number, for several criteria of minimality.
Since digons are similar to undirected edges, their impact on colorability of graphs has already been studied very extensively. Hence, we will give special attention to the colorability of oriented (or digon-free) graphs.

Category: seminars
Tags: Team seminar networks