So What’s Graph Coloring Anyway?

A graph is a set of dots connected by links. Dots are often called vertices, and links are often called edges. A (vertex) coloring is an assignment of colors to the dots so that any two connected dots have different colors.
Finding a graph coloring is (often) a very hard problem, as it in the worst case requires an exponential number of steps to figure out. The problem belongs to a class of problems called “NP-complete”.
Chrome-8, the iPhone game, is a fun way of getting an understanding of what graph coloring is, and how difficult it can be to solve!

One Response to “So What’s Graph Coloring Anyway?”

  1. […] are many problems that are found to be NP-complete, for instance Graph Coloring, the basis for my puzzle […]