Geodesic
Iterated arc graphs
Commentationes Mathematicae Universitatis Carolinae, Tome 59 (2018) no. 3, pp. 277-283.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
DOI : 10.14712/1213-7243.2015.260
Classification : 05C15, 06A07
Keywords: arc graph; chromatic number; free distributive lattice; Dedekind number 
@article{10_14712_1213_7243_2015_260,
     author = {Rorabaugh, Danny and Tardif, Claude and Wehlau, David and Zaguia, Imed},
     title = {Iterated arc graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {277--283},
     publisher = {mathdoc},
     volume = {59},
     number = {3},
     year = {2018},
     doi = {10.14712/1213-7243.2015.260},
     mrnumber = {3861552},
     zbl = {06940870},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2015.260/}
}
TY  - JOUR
AU  - Rorabaugh, Danny
AU  - Tardif, Claude
AU  - Wehlau, David
AU  - Zaguia, Imed
TI  - Iterated arc graphs
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 2018
SP  - 277
EP  - 283
VL  - 59
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2015.260/
DO  - 10.14712/1213-7243.2015.260
LA  - en
ID  - 10_14712_1213_7243_2015_260
ER  - 
%0 Journal Article
%A Rorabaugh, Danny
%A Tardif, Claude
%A Wehlau, David
%A Zaguia, Imed
%T Iterated arc graphs
%J Commentationes Mathematicae Universitatis Carolinae
%D 2018
%P 277-283
%V 59
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2015.260/
%R 10.14712/1213-7243.2015.260
%G en
%F 10_14712_1213_7243_2015_260
Rorabaugh, Danny; Tardif, Claude; Wehlau, David; Zaguia, Imed. Iterated arc graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 59 (2018) no. 3, pp. 277-283. doi : 10.14712/1213-7243.2015.260. http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2015.260/

Cité par Sources :