1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

An Improved Bound on the Chromatic Number of the Pancake Graphs

Published Online: 08 Oct 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 15 Mar 2021
Accepted: 10 Sep 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

In this paper, an improved bound on the chromatic number of the Pancake graph Pn, 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 Pn. 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 Pn coincides with its equitable chromatic number for any n ⩾ 2.

Keywords

MSC 2010

[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:100839420599910.1023/A:1008394205999Search in Google Scholar

[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.2163410.1002/jcd.21634Search in Google Scholar

[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-710.1007/s10623-007-9100-7Search in Google Scholar

[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/S030500410002168X10.1017/S030500410002168XSearch in Google Scholar

[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-510.1016/0095-8956(77)90037-5Search in Google Scholar

[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-310.1016/0012-365X(78)90049-3Search in Google Scholar

[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-X10.1016/0012-365X(78)90167-XSearch in Google Scholar

[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.104710.1006/eujc.1994.1047Search in Google Scholar

[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-510.1016/S0166-218X(02)00573-5Search in Google Scholar

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

[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-410.1007/s11202-007-0075-4Search in Google Scholar

[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.199210.7151/dmgt.1992Search in Google Scholar

[13] H. Ghodrati, (private communications), 04.04.2019.Search in Google Scholar

[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-110.1016/S0024-3795(97)83595-1Search in Google Scholar

[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-S10.1016/0167-8191(94)00096-SSearch in Google Scholar

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

[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/S000497270004023510.1017/S0004972700040235Search in Google Scholar

[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_2310.1007/978-3-642-36899-8_23Search in Google Scholar

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

[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.Search in Google Scholar

[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_2510.1007/978-1-4419-7997-1_25Search in Google Scholar

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

[23] T. Pisanski, (private communications), 01.09.2015.Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo