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, S.\ Poljak and V.\ R\"{o}dl characterized 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. Our proof is a rediscovery of the proof of [Poljak S., {\it Coloring digraphs by iterated antichains}, Comment. Math. Univ. Carolin. {\bf 32} (1991), no. 2, 209--212], though various mistakes make the original proof unreadable.
Keywords: arc graph; chromatic number; free distributive lattice; Dedekind number
DOI: DOI 10.14712/1213-7243.2015.260
AMS Subject Classification: 05C15 06A07