10.30495/ijm2c.2022.1954367.1250

The Chromatic Number of the Square of the Cartesian Product of Cycles and Paths

PDF
  • Sajad Sohrabi Hesan1,
  • Freydoon Rahbarnia*1,
  • Mostafa Tavakoli1,
  1. Department of Applied Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad, Iran

Received: 12-03-2022

Accepted: 13-08-2022

Published in Issue 01-09-2022

Copyright (c) 2024 International Journal of Mathematical Modeling & Computations

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

Sohrabi Hesan, S., Rahbarnia, F., & Tavakoli, M. (2022). The Chromatic Number of the Square of the Cartesian Product of Cycles and Paths. International Journal of Mathematical Modelling & Computations, 12(3), 191-199. https://doi.org/10.30495/ijm2c.2022.1954367.1250
Crossref
Scopus
Google Scholar
Europe PMC

Abstract

Given any graph G, its square graph G^2 has the same vertex set V (G), with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. A set S ⊆ V (G) is a 2-distance independent set of a graph G if the distance between every two vertices of S is greater than 2. The 2-distance independence number α_2(G) of G is the maximum cardinality over all 2-distance independent sets in G. In this paper, we establish the 2-distance independence number and 2-distance chromatic number for C_3□C_6□C_m, C_n□P_3□P_3 and C_4□C_7□C_n where m ≡ 0 (mod 3) and n,m ⩾ 3.
PDF

References

  1. S. Bakaein, M. Tavakoli, A. R. Ashrafi and O. Ori, Coloring of fullerenes, Fullerenes, Nanotubes and
  2. Carbon Nanostructures, 26 (2018) 1–4.
  3. A. G. Chegini, M. Hasanvand, E. S. Mahmoodian and F. Moazam, The square chromatic number
  4. of the torus, Discrete Math., 339 (2016) 447– 456.
  5. S. H. Chiang and J. H. Yan, On L.d; 1-labeling of Cartesian product of a cycle and a path, Discrete
  6. Appl. Math., 156 (2008) 2867–2881.
  7. Z. Dvok, D. Krl, P. Nejedl and R. krekovski, Coloring squares of planar graphs with girth six,
  8. European J. Combin., 4 (2008) 838–849.
  9. F. Havet, J. van den Heuvel, C. J. H. McDiarmid and B. Reed, List colouring squares of planar
  10. graphs, in: Proc. 2007 Europ. Conf. on Combin, Graph Theory and Applications, EuroComb’07, in:
  11. Electr. Notes in Discrete Math., 29 (2007) 515–519.
  12. R. E. Jamison, G. L. Matthews and J. Villalpando, Acyclic colorings of products of trees, Inform.
  13. Process. Lett., 99 (2006) 7–12.
  14. S. Klavˇzar and M. Tavakoli, Dominated and dominator colorings over (edge) corona and hierarchical
  15. products, Appl. Math. Comput., 390 (2021) 125647.
  16. K. W. Lih and W. Wang, Coloring the square of an outerplanar graph, Taiwanese J. Math., 10
  17. (2006) 1015–1023.
  18. T. Manjula and R. Rajeswari, Domiator chromatic number of some graphs, International Journal of
  19. Pure and Applied Mathematics, 119 (2018) 787–795.
  20. M. Molloy and M. R. Salavatipour, A bound on the chromatic number of the square of a planar
  21. graph, J. Combin. Theory Ser. B , 94 (2) (2005) 189–213.
  22. Z. Shao and A. Vesel, A note on the chromatic number of the square of the Cartesian product of
  23. two cycles, Discrete Math., 313 (9) (2013) 999–1001.
  24. Z. Shao, A. Vesel and J. Xu , The k-distance independence number and 2-distance chromatic number
  25. of Cartesian products of cycles, Bull. Malays. Math. Sci. Soc., 41 (2016) 1377–1391.
  26. E. Sopena and J. Wu, Coloring the square of the Cartesian product of two cycles, Discrete Math.,
  27. (2010) 2327–2333.
  28. J. J. Sylvester, Mathematical questions with their solutions, Educ. Times, 41 (1884) 171–178.
  29. J. Van den Heuvel and S. McGuinness, Coloring the square of a planar graph, Probab. Engrg. Inform.
  30. Sci. J. Graph Theory, 42 (2002) 110–124.
  31. G. Wegner, Graphs with given diameter and a colouring problem, Technical Report, University of
  32. Dortmund, (1977)