The Smallest Number of Colors Needed for a‎ ‎Coloring of the Square of the Cartesian Product of Certain Graphs

Given any graph G‎, ‎its square graph G^2 has the same vertex set as G, ‎with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. ‎‎The Cartesian product of graphs G and H is denoted by G□ H. ‎‎One of the most studied NP-hard problems is the graph coloring problem‎. A method such as Genetic Algorithm (GA) is highly preferred to solve the Graph Coloring problem by researchers for many years‎. ‎In this paper‎, ‎we use the graph product approach to this problem‎. ‎In fact‎, ‎we prove that X((D(m',n')□D(m,n))^2)<= 10 for m,n => 3, ‎where D(m‎, ‎n) is the graph obtained by joining a vertex of the cycle C_m to a vertex of degree one of the paths P_n and X(G) is the chromatic number of the graph G.

The Smallest Number of Colors Needed for a‎ ‎Coloring of the Square of the Cartesian Product of Certain Graphs Keywords:

2-Distance coloring‎ , ‎Chromatic number‎ , ‎Cartesian product‎ , ‎Dragon graph