A vertex coloring is an assignment of labels or colors to each vertex of a graph wach that no edge connects two identically colored vertices. The most common type of vertex coloring seeks to minimize the number of colors for a given graph.