Some results on directed coloring
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.