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

International Journal of Mathematical Modelling & Computations

مقاله 5، دوره 12، 3 (SUMMER) - شماره پیاپی 47، آذر 2022، صفحه 191-199   

نوع مقاله: Full Length Article

شناسه دیجیتال (DOI): 10.30495/ijm2c.2022.1954367.1250

نویسندگان

Sajad Sohrabi Hesan؛ Freydoon Rahbarnia^* ؛ Mostafa Tavakoli

Department of Applied Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad, Iran

چکیده

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.

کلیدواژه‌ها

2-Distance coloring؛ Chromatic number؛ Cartesian product؛ 2-Distance independent set