Irreducible coverings by cliques and Sperner's theorem.
The arc graph of a digraph is the digraph with the set of arcs of as vertex-set, where the arcs of join consecutive arcs of . In 1981, S. Poljak and V. Rödl characterized the chromatic number of in terms of the chromatic number of when is symmetric (i.e., undirected). In contrast, directed graphs with equal chromatic numbers can have arc graphs with distinct chromatic numbers. Even though the arc graph of a symmetric graph is not symmetric, we show that the chromatic number of the...