×

Iterated arc graphs. (English) Zbl 1463.05188

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 [J. Comb. Theory, Ser. B 31, 190–198 (1981; Zbl 0472.05024)], 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 S. Poljak [Commentat. Math. Univ. Carol. 32, No. 2, 209–212 (1991; Zbl 0758.05053)], though various mistakes make the original proof unreadable.

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Dilworth R. P., A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161-166 · Zbl 0038.02003
[2] Foniok J.; Tardif C., Digraph functors which admit both left and right adjoints, Discrete Math. 338 (2015), no. 4, 527-535 · Zbl 1305.05087
[3] Harner C. C.; Entringer R. C., Arc colorings of digraphs, J. Combinatorial Theory Ser. B 13 (1972), 219-225 · Zbl 0231.05105
[4] Hell P.; Nešetřil J., Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications, 28, Oxford University Press, Oxford, 2004 · Zbl 1062.05139
[5] Markowsky G., The level polynomials of the free distributive lattices, Discrete Math. 29 (1980), no. 3, 275-285 · Zbl 0439.06009
[6] McHard R. W., Sperner Properties of the Ideals of a Boolean Lattice, Ph.D. Thesis, University of California, Riverside, 2009
[7] Poljak S., Coloring digraphs by iterated antichains, Comment. Math. Univ. Carolin. 32 (1991), no. 2, 209-212 · Zbl 0758.05053
[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 · Zbl 0472.05024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.