Graph coloring is the study of assigning a color to each vertex such that no vertex has the same color as any other to which it is connected. It is also possible to consider edge-coloring of graphs where each edge may not have the same color of any other edge that is connected to the same vertices, however, I chose to focus on vertex-coloring. While it is trivial to color a graph on N vertices with N colors, it is often desirable to color graphs with the fewest possible number of unique colors. Graph three-coloring is the study of coloring a graph with only three unique colors. Graph three-coloring is an NP-Complete problem.



What are NP-Complete Problems?