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

محورهای موضوعی : فصلنامه ریاضی

Sajad Sohrabi Hesan ¹ (Department of Applied Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad, Iran)
Freydoon Rahbarnia ² (Department of Applied Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad, Iran)
Mostafa Tavakoli ³ (Department of Applied Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad, Iran)

تاریخ دریافت : 1400/12/21 تاریخ پذیرش : 1401/05/22 تاریخ انتشار : 1401/06/10

کلید واژه: 2-Distance coloring, Chromatic number, Cartesian product, 2-Distance independent set,

چکیده مقاله :

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.