Vertex-Distinguishing Edge Colorings Of Some Complete Multipartite Graphs

In graph theory, an edge coloring of a graph is a coloring of the edges, meaning an assignment of colors to edges. Edge coloring can be described as function , where is the set of graph edges and is the set of natural numbers. Graph coloring has been studied as an algorithmic problem since the early 1970s. The main objective is to minimize the number of colors while coloring a graph. The smallest number of colors required to color a graph with specified conditions is called chromatic number of that graph and is denoted by . By a result of Holyer [1], the determination of the chromatic index is an hard optimization problem. The NP-hardness give rise to the necessity of using heuristic algorithms. In particular, we are interested in upper bounds for the chromatic index that can be efficiently realized by a coloring algorithm.