Title : ( The smallest number of colors needed for a coloring of the square of the Cartesian product of certain graphs )
Authors: sajad sohrabi hesan , Freydoon Rahbarnia , Mostafa Tavakoli ,
دانلود فایل برای اعضای دانشگاهAccess to full-text not allowed by authors
Abstract
Given any graph G, its square graph G2 has the same vertex set as G, with two vertices adjacent in G2 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. Method such as Genetic Algorithm (GA) is highly preferred to solve the Graph Coloring problem by the researchers for many years. In this paper, we use the graph product approach to this problem. In fact, we prove that χ((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 Cm to a vertex of degree one of the path Pn and χ(G) is the chromatic number of the graph G.
Keywords
, 2-Distance coloring, Chromatic number, Cartesian product, Dragon graph
@article{paperid:1091785,
author = {Sohrabi Hesan, Sajad and Rahbarnia, Freydoon and Tavakoli, Mostafa},
title = {The smallest number of colors needed for a coloring of the square of the Cartesian product of certain graphs},
journal = {Control and Optimization in Applied Mathematics},
year = {2023},
volume = {8},
number = {1},
month = {June},
issn = {2383-3130},
pages = {83--93},
numpages = {10},
keywords = {2-Distance coloring; Chromatic number; Cartesian product; Dragon
graph},
}
%0 Journal Article
%T The smallest number of colors needed for a coloring of the square of the Cartesian product of certain graphs
%A Sohrabi Hesan, Sajad
%A Rahbarnia, Freydoon
%A Tavakoli, Mostafa
%J Control and Optimization in Applied Mathematics
%@ 2383-3130
%D 2023
