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.