| Title:
|
Iterated arc graphs (English) |
| Author:
|
Rorabaugh, Danny |
| Author:
|
Tardif, Claude |
| Author:
|
Wehlau, David |
| Author:
|
Zaguia, Imed |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
59 |
| Issue:
|
3 |
| Year:
|
2018 |
| Pages:
|
277-283 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
arc graph |
| Keyword:
|
chromatic number |
| Keyword:
|
free distributive lattice |
| Keyword:
|
Dedekind number |
| MSC:
|
05C15 |
| MSC:
|
06A07 |
| idZBL:
|
Zbl 06940870 |
| idMR:
|
MR3861552 |
| DOI:
|
10.14712/1213-7243.2015.260 |
| . |
| Date available:
|
2018-09-10T12:07:07Z |
| Last updated:
|
2020-10-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147397 |
| . |
| Reference:
|
[1] Dilworth R. P.: A decomposition theorem for partially ordered sets.Ann. of Math. (2) 51 (1950), 161–166. MR 0032578, 10.2307/1969503 |
| Reference:
|
[2] Foniok J., Tardif C.: Digraph functors which admit both left and right adjoints.Discrete Math. 338 (2015), no. 4, 527–535. MR 3300740, 10.1016/j.disc.2014.10.018 |
| Reference:
|
[3] Harner C. C., Entringer R. C.: Arc colorings of digraphs.J. Combinatorial Theory Ser. B 13 (1972), 219–225. MR 0313101, 10.1016/0095-8956(72)90057-3 |
| Reference:
|
[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 |
| Reference:
|
[5] Markowsky G.: The level polynomials of the free distributive lattices.Discrete Math. 29 (1980), no. 3, 275–285. MR 0560771, 10.1016/0012-365X(80)90156-9 |
| Reference:
|
[6] McHard R. W.: Sperner Properties of the Ideals of a Boolean Lattice.Ph.D. Thesis, University of California, Riverside, 2009. MR 2718021 |
| Reference:
|
[7] Poljak S.: Coloring digraphs by iterated antichains.Comment. Math. Univ. Carolin. 32 (1991), no. 2, 209–212. MR 1137780 |
| Reference:
|
[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. MR 0630982, 10.1016/S0095-8956(81)80024-X |
| . |
