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.
2 January 2022 in AKCE International Journal of Graphs and Combinatorics
A small-world Farey graph is a recursively constructed graph characterized as a small-world network graph. Many of the network properties of this graph has been studied. In this paper, we take a combinatorial approach to investigate the rainbow vertex connectivity of the small-world Farey graph. A graph is rainbow vertex-connected when there exists a path, in which all of its internal vertices have distinct colors, between each pair of vertices. We give a coloring so that the graph is rainbow vertex-connected. The rainbow vertex-connection number of the small-world Farey graph, which is the minimum number of colors needed so that the graph is rainbow vertex-connected, is one less than the diameter of the graph.
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 among cycles, paths, and stars.
This study examines the δ-complements of graphs—a specific type of graph complement whose adjacency depends on the adjacency of the vertices with identical degrees in the original graph. More specifically, we study this type of complement regarding the domination number. We provide sharp Nordhaus-Gaddum-type bounds on the domination number of a graph and its δ-complement. We also provide sharp bounds on the domination numbers of the δ-complements of joined graphs and Cartesian product graphs.
1 August 2025 in European Journal of Pure and Applied Mathematics
A b-coloring of a graph G is a proper coloring such that there exists a vertex in each color class that is adjacent to at least one vertex in other color classes. The b-chromatic number of a graph G, denoted by φ(G), is the largest integer k such that G has b-coloring with k colors. The b-chromatic sum of graph G, denoted by φ′(G), is defined as the minimum sum of the colors c(v) of v for all v ∈ V where c is a b-coloring with colors 1, 2, . . . , φ(G). In the work, we improve the bounds on the b-chromatic sum given by Lisna and Sunitha [4]. We give the b-chromatic sum of the Mycielskian of a path μ(Pn) when n = 7, 9 and n ≥ 16. For the case 10 ≤ n ≤ 15, we give bounds on φ′(μ(Pn)).
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.