Geodesic
An improved bound on the chromatic number of the Pancake graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 35-46 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

In this paper, an improved bound on the chromatic number of the Pancake graph P_n, n⩾ 9, is presented. The bound is obtained using a subadditivity property of the chromatic number of the Pancake graph. We also investigate an equitable coloring of P_n. An equitable (n-1)-coloring based on efficient dominating sets is given and optimal equitable 4-colorings are considered for small n. It is conjectured that the chromatic number of P_n coincides with its equitable chromatic number for any n ⩾ 2.
Keywords: Pancake graph, chromatic number, equitable coloring 
@article{DMGT_2024_44_1_a2,
     author = {Droogendijk, Leen and Konstantinova, Elena},
     title = {An improved bound on the chromatic number of the {Pancake} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {35--46},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a2/}
}
TY  - JOUR
AU  - Droogendijk, Leen
AU  - Konstantinova, Elena
TI  - An improved bound on the chromatic number of the Pancake graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 35
EP  - 46
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a2/
LA  - en
ID  - DMGT_2024_44_1_a2
ER  - 
%0 Journal Article
%A Droogendijk, Leen
%A Konstantinova, Elena
%T An improved bound on the chromatic number of the Pancake graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 35-46
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a2/
%G en
%F DMGT_2024_44_1_a2
Droogendijk, Leen; Konstantinova, Elena. An improved bound on the chromatic number of the Pancake graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 35-46. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a2/

[1] R. Ahlswede, H. Aydinian and L. Khachatrian, On perfect codes and related concepts, Des. Codes Cryptogr. 22 (2001) 221–237. https://doi.org/10.1023/A:1008394205999

[2] R.A. Bailey, P.J. Cameron, A.L. Gavrilyuk and S.V. Goryainov, Equitable partitions of Latin-square graphs, J. Combin. Des. 27 (2019) 142–160. https://doi.org/10.1002/jcd.21634

[3] A. Blokhuis, A.E. Brouwer and W.H. Haemers, On 3-chromatic distance-regular graphs, Des. Codes Cryptogr. 44 (2007) 293–305. https://doi.org/10.1007/s10623-007-9100-7

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

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

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

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

[8] B.-L. Chen, K.-W. Lih and P.-L Wu, Equitable coloring and the maximum degree, European J. Combin. 15 (1994) 443–447. https://doi.org/10.1006/eujc.1994.1047

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

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

[11] D.G. Fon-Der-Flaass, Perfect 2-colorings of a hypercube, Sib. Math. J. 48 (2007) 740–745. https://doi.org/10.1007/s11202-007-0075-4

[12] H. Furmańczyk, M. Kubale and V.V. Mkrtchyan, Equitable colorings of corona multiproducts of graphs, Discuss. Math. Graph Theory 37 (2017) 1079–1094. https://doi.org/10.7151/dmgt.1992

[13] H. Ghodrati, (private communications), 04.04.2019.

[14] C.D. Godsil, Compact graphs and equitable partitions, Linear Algebra Appl. 255 (1997) 259–266. https://doi.org/10.1016/S0024-3795(97)83595-1

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

[16] J.H. Kim, On Brooks’ theorem for sparse graphs, Combin. Probab. Comput. 4 (1995) 97–132. https://doi.org/10.1017/S0963548300001528

[17] S. Klavžar, U. Milutinović and C. Petr, 1-perfect codes in Sierpiński graphs, Bull. Aust. Math. Soc. 66 (2002) 369–384. https://doi.org/10.1017/S0004972700040235

[18] E.V. Konstantinova, On some structural properties of star and Pancake graphs, in: Information Theory, Combinatorics, and Search Theory, Lecture Notes in Comput. Sci. 7777 (2013) 472–487. https://doi.org/10.1007/978-3-642-36899-8_23

[19] E.V. Konstantinova, Chromatic properties of the Pancake graphs, Discuss. Math. Graph Theory 37 (2017) 777–787. https://doi.org/10.7151/dmgt.1978

[20] E.V. Konstantinova and A.N. Medvedev, Cycles of length seven in the Pancake graph, Diskretn. Anal. Issled. Oper. 17 (2010) 46–55, in Russian.

[21] K.W. Lih, Equitable coloring of graphs, in: Handbook of Combinatorial Optimization, P. Pardalos, D.Z. Du and R. Graham (Ed(s)), (Springer, New York 2013) 1199–1248. https://doi.org/10.1007/978-1-4419-7997-1_25

[22] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973) 920–922. https://doi.org/10.1080/00029890.1973.11993408

[23] T. Pisanski, (private communications), 01.09.2015.

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

[25] 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.