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)

تاريخ الإرسال : 09 السبت , شعبان, 1443 تاريخ التأكيد : 15 السبت , محرم, 1444 تاريخ الإصدار : 05 الخميس , صفر, 1444

الکلمات المفتاحية: 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.