The Smallest Number of Colors Needed for a Coloring of the Square of the Cartesian Product of Certain Graphs
نویسندگان
1 Department of Applied Mathematics, Ferdowsi University of Mashhad, P.O. Box 1159, Mashhad 91775, Iran.
2 Department of Applied Mathematics, Ferdowsi University of Mashhad, P.O. Box 1159, Mashhad 91775, Iran.
3 Department of Applied Mathematics, Ferdowsi University of Mashhad, P.O. Box 1159, Mashhad 91775, Iran.
doi
10.30473/coam.2022.54855.1194چکیده
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$.
