Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
arc graph; chromatic number; free distributive lattice; Dedekind number
arc graph; chromatic number; free distributive lattice; Dedekind number
Summary:
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ö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., {Coloring digraphs by iterated antichains}, Comment. Math. Univ. Carolin. {32} (1991), no. 2, 209-212], though various mistakes make the original proof unreadable.
References:
[1] Dilworth R. P.: A decomposition theorem for partially ordered sets. Ann. of Math. (2) 51 (1950), 161–166. DOI 10.2307/1969503 | MR 0032578
[2] Foniok J., Tardif C.: Digraph functors which admit both left and right adjoints. Discrete Math. 338 (2015), no. 4, 527–535. DOI 10.1016/j.disc.2014.10.018 | MR 3300740
[3] Harner C. C., Entringer R. C.: Arc colorings of digraphs. J. Combinatorial Theory Ser. B 13 (1972), 219–225. DOI 10.1016/0095-8956(72)90057-3 | MR 0313101
[4] Hell P., Nešetřil J.: Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications, 28, Oxford University Press, Oxford, 2004. MR 2089014
[5] Markowsky G.: The level polynomials of the free distributive lattices. Discrete Math. 29 (1980), no. 3, 275–285. DOI 10.1016/0012-365X(80)90156-9 | MR 0560771
[6] McHard R. W.: Sperner Properties of the Ideals of a Boolean Lattice. Ph.D. Thesis, University of California, Riverside, 2009. MR 2718021
[7] Poljak S.: Coloring digraphs by iterated antichains. Comment. Math. Univ. Carolin. 32 (1991), no. 2, 209–212. MR 1137780
[8] Poljak S., Rödl V.: On the arc-chromatic number of a digraph. J. Combin. Theory Ser. B 31 (1981), no. 2, 190–198. DOI 10.1016/S0095-8956(81)80024-X | MR 0630982
Search
Partner of
