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

Given any graph G, its square graph G^۲ has the same vertex set V (G), with two vertices adjacent in G^۲ whenever they are at distance ۱ or ۲ in G. A set S ⊆ V (G) is a ۲-distance independent set of a graph G if the distance between every two vertices of S is greater than ۲. The ۲-distance independence number α_۲(G) of G is the maximum cardinality over all ۲-distance independent sets in G. In this paper, we establish the ۲-distance independence number and ۲-distance chromatic number for C_۳□C_۶□C_m, C_n□P_۳□P_۳ and C_۴□C_۷□C_n where m ≡ ۰ (mod ۳) and n,m ⩾ ۳.

Keywords:

۲-Distance coloring , Chromatic number , Cartesian product , ۲-Distance independent set