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

2024/01/01 by Tangjai, Wipawee, Pho-on, Witsarut, Vichitkunakorn, Panupong
#05C07 #05C15 #05C35 #05C38 #05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2401.00666

Abstract

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

Related

• On the b-chromatic number of star graph operators
• On the b-chromatic number of the Cartesian product of two complete graphs
• The Chromatic Number of the Square of the Cartesian Product of Cycles and Paths
• Star Edge Coloring of the Cartesian Product of Graphs
• On the Locating Chromatic Number of the Cartesian Product of Graphs