On the Maximization of Some Graph Coloring Problems
A graph coloring problem involves labeling the vertices or edges in a graph with newlinecolors or numbers subject to some constraints. The most frequently known graph newlinecoloring problems are the ones that usually minimize the number of colors used in newlinecoloring the vertices or edges. The chromatic number of a graph G, denoted by and#967;(G), is the least number of colors used in a proper coloring of G. The chromatic sum of a graph G, denoted as P(G), was introduced in [1], which is to and the smallest possible coloring sum in a proper coloring of the graph G using natural numbers. Lately, a few studies have endured in a distinct area of the literature where the number of colors used in a graph coloring problem is maximized under certain conditions. Some of these works have applications in network sciences. newlineThe concerned study focuses on the maximization of three dierent edge coloring newlineconcepts, viz., the vertex induced kand#8722;edge coloring, vertex incident kand#8722;edge coloring, newlineand edge incident 2and#8722;edge coloring of a simple connected graph G, where k and#8805; 2. The newlinenumber of colors assigned to the edges of the graph G has been maximized under certain conditions. The vertex induced kand#8722;edge coloring and the vertex incident newlinekand#8722;edge coloring concepts are the generalized version of the edge coloring approach newlineintroduced and studied in [2]. Furthermore, the concept of the achromatic sum of a graph G has also been introduced here. This concept is to and the greatest possible coloring sum of the graph G in an improper edge coloring using natural numbers. An extensive study newlineon three achromatic sums, namely the vertex induced 2and#8722;edge coloring sum, the vertex incident 2and#8722;edge coloring sum, and the edge incident 2and#8722;edge coloring sum are carried out. A few bounds for these parameters on a simple connected graph G and the exact values for some elementary graph classes have been investigated. A few comparative results between some of these parameters have also been obtained.