A REVIEW ON THE CHROMATIC NUMBER OF CARTESIAN PRODUCTS AND APPLICATIONS

Abstract

Given any graph G, its square graph G2 has the same
vertex set V (G), with two vertices adjacent in G2
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 C3>C6>Cm, Cn>P3>P3 and C4>C7>Cn where m ≡ 0
(mod 3) and n, m ⩾ 3.