ABSTRACT
Solutions to scheduling and assignment problems strive to avoid conflicts or incompatibilities while seeking to optimize various criteria. Such problems can be modeled using graphs with the focus either on vertex coloring or on edge matching. The concept of vertex coloring involves assigning different colors to adjacent vertices so that all vertices are colored and the fewest colors are used. The idea behind edge matching involves choosing edges that have no vertices in common and choosing as many such non-adjacent edges as possible. Similar to the Traveling Salesman Problem, there are no known efficient solution techniques that are guaranteed to find the fewest colors needed in a vertex coloring (the chromatic number of the graph). Several heuristic (approximate) techniques have been developed for coloring a graph, and we illustrate the Greedy Coloring Algorithm, perhaps the simplest technique for sequentially assigning colors to the vertices. By contrast, there are efficient techniques for determining the largest size of an edge matching in a graph.
