On the δ-chromatic numbers of the Cartesian products of graphs

Abstract

In this work, we study the δ\delta -chromatic number of a graph, which is the chromatic number of the δ\delta -complement of a graph. We give a structure of the δ\delta -complements and sharp bounds on the δ\delta -chromatic numbers of the Cartesian products of graphs. Furthermore, we compute the δ\delta -chromatic numbers of various classes of Cartesian product graphs, including the Cartesian products among cycles, paths, and stars.

Keywords

• δ-complement graph
• chromatic number
• cartesian product
• coloring
• 05c07
• 05c15
• 05c35
• 05c38
• 05c69