DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

L. Droogendijk

Leen Droogendijk

with no affiliation

email: drooge001@kpnmail.nl

E.V. Konstantinova

Elena V. Konstantinova

Sobolev Institute of Mathematics, Novosibirsk State University

email: e_konsta@math.nsc.ru

0000-0002-3457-645X

Title:

An improved bound on the chromatic number of the Pancake graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 44(1) (2024) 35-46

Received: 2021-03-15 , Revised: 2021-09-08 , Accepted: 2021-09-10 , Available online: 2021-09-22 , https://doi.org/10.7151/dmgt.2432

Abstract:

In this paper, an improved bound on the chromatic number of the Pancake graph $P_n, n\geqslant 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\geqslant 2$.

Keywords:

Pancake graph, chromatic number, equitable coloring

References:

  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.
Close