Iterated Arc Graphs

Abstract

The arc graph $\delta (G)$ of a digraph $G$ is the digraph with the set of arcs of $G$ as vertex-set, where the arcs of $\delta (G)$ join consecutive arcs of $G$. In 1981, Poljak and Rödl characterised the chromatic number of $\delta (G)$ in terms of the chromatic number of $G$ when $G$ 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 iterated arc graph ${\delta }^k(G)$ still only depends on the chromatic number of $G$ when $G$ is symmetric.

7 pages