Geodesic
Chromatic Properties of the Pancake Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 777-787

Voir la notice de l'article provenant de la source Library of Science

Chromatic properties of the Pancake graphs Pn, n ⩾ 2, that are Cayley graphs on the symmetric group Symn generated by prefix-reversals are investigated in the paper. It is proved that for any n ⩾ 3 the total chromatic number of Pn is n, and it is shown that the chromatic index of Pn is n − 1. We present upper bounds on the chromatic number of the Pancake graphs Pn, which improve Brooks’ bound for n ⩾ 7 and Katlin’s bound for n ⩽ 28. Algorithms of a total n-coloring and a proper (n − 1)-coloring are given.
Keywords: Pancake graph, Cayley graphs, symmetric group, chromatic number, total chromatic number 
Konstantinova, Elena. Chromatic Properties of the Pancake Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 777-787. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a18/
@article{DMGT_2017_37_3_a18,
     author = {Konstantinova, Elena},
     title = {Chromatic {Properties} of the {Pancake} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {777--787},
     year = {2017},
     volume = {37},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a18/}
}
TY  - JOUR
AU  - Konstantinova, Elena
TI  - Chromatic Properties of the Pancake Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 777
EP  - 787
VL  - 37
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a18/
LA  - en
ID  - DMGT_2017_37_3_a18
ER  - 
%0 Journal Article
%A Konstantinova, Elena
%T Chromatic Properties of the Pancake Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 777-787
%V 37
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a18/
%G en
%F DMGT_2017_37_3_a18

[1] O.V. Borodin and A.V. Kostochka, On an upper bound of a graph’s chromatic number depending on the graph’s degree and destiny, J. Combin. Theory. Ser. B. 23 (1977) 247-250. doi:10.1016/0095-8956(77)90037-5

[2] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194–197. doi:10.1017/S030500410002168X

[3] P.A. Catlin, A bound on the chromatic number of a graph, Discrete Math. 22 (1978) 81–84. doi:10.1016/0012-365X(78)90049-3

[4] P.A. Catlin, Another bound on the chromatic number of a graph, Discrete Math. 24 (1978) 1–6. doi:10.1016/0012-365X(78)90167-X

[5] I.J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003) 319–328. doi:10.1016/S0166-218X(02)00573-5

[6] H. Dweighter, E 2569 in: Elementary problems and solutions, Amer. Math. Monthly 82 (1975) 1010.

[7] A. Johansson, Asymptotic choice number for triangle free graphs, DIMACS Technical Report (1996) 91–95.

[8] A. Kanevsky and C. Feng, On the embedding of cycles in Pancake graphs, Parallel Comput. 21 (1995) 923–936. doi:10.1016/0167-8191(94)00096-S

[9] E. Konstantinova, On some structural properties of Star and Pancake graphs, Lecture Notes in Comput. Sci. 7777 (2013) 472–487. doi:10.1007/978-3-642-36899-8_23

[10] E. Konstantinova and A. Medvedev, Independent even cycles in the Pancake graph and greedy Prefix-reversal Gray codes, Graphs Combin. 32 (2016) 1965–1978. doi:10.1007/s00373-016-1679-x

[11] J.J. Sheu, J.J.M. Tan and K.T. Chu, Cycle embedding in Pancake interconnection networks, in: Proc. 23rd Workshop on Combinatorial Mathematics and Computation Theory (Taiwan, 2006) 85–92.

[12] K. Qiu, Optimal broadcasting algorithms for multiple messages on the Star and Pancake graphs using minimum dominating sets, Congr. Numer. 181 (2006) 33–39.

[13] V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk 23 (1968) 117–134. doi:10.1070/rm1968v023n06abeh001252