On Nordhaus-Gaddum type relations of δ-complement graphs

Abstract

The δ-complement graphs were introduced by Amrithalakshmi et al. in 2022. In their work, some interesting properties of the graphs such as δ-self-complementary, adjacency, and hamiltonicity were studied. In this work, we study the coloring aspect of the δ-complement graphs. In particular, we provide lower and upper bounds on the product and the summation between the chromatic number and the δ-chromatic number of a graph, in the same fashion as the well-known Nordhaus-Gaddum type relations. Classes of graphs that achieve those bounds are also given. Furthermore, we provide upper bounds on δ-chromatic numbers in terms of the clique numbers and compute the δ-chromatic numbers of certain graphs including ladder graphs, path graphs, complete m-partite graphs, and small-world Farey graphs.

Keywords

• Delta-complement graph
• Chromatic number
• Nordhaus-Gaddum
• Coloring
• Small-world Farey graph