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

Subject Areas : International Journal of Mathematical Modelling & Computations

Sajad Sohrabi Hesan ¹ , Freydoon Rahbarnia ² , Mostafa Tavakoli ³

1 - Department of Applied Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad, Iran
2 - Department of Applied Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad, Iran
3 - Department of Applied Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad, Iran

Received: 2022-03-12 Accepted : 2022-08-13 Published : 2022-09-01

Keywords: 2-Distance coloring, Chromatic number, Cartesian product, 2-Distance independent set,

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.

References:

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