Graph three-coloring has been shown to be in a class of problems known as NP-Complete. In a nutshell, NP-Complete problems are considered the hardest problems in the class of non-deterministically solvable problems given the constraint of polynomial time. [1] In essence, these problems cannot be solved by a deterministic computer (such as all current computer models based on a Turing-machine) in less than exponential time. Another interesting fact about all NP-Complete problems is that every problem in this class can be mapped to any other in polynomial time. This implies that if a polynomial time algorithm were found for a single problem in this class, we could then find a polynomial time algorithm for all problems in this class. As of current research, there is no proof showing that a polynomial time algorithm does or does not exist for these problems. [1]

Some Examples of NP-Complete Problems:

• Integer partitioning
  • Partition N integers into two subsets such that the sum of each subset is equal.
• Bin packing
  • How many bins of a given size are needed to hold N items of variable size.
• Chromatic number
  • Find the minimum number of colors needed to properly vertex-color a graph.