Graph coloring
Graph coloring is the name for a number of problems from graph theory. These problems are concerned with coloring (or labelling) the vertices of a graph, given certain conditions. A simple problem in this context might look for the minimal number of colors needed to color the vertices, when two connected vertices cannot have the same color. In the graph shown, the circles are called vertices and the lines connecting them are called edges. The minimum number of colors needed to color a graph is called its chromatic number.
Graph Coloring Media
A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible.
A map of the United States using colors to show political divisions using the four color theorem.
This graph can be 3-colored in 12 different ways.
All non-isomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph E3 (red) admits a 1-coloring; the complete graph K3 (blue) admits a 3-coloring; the other graphs admit a 2-coloring.
A graph with a 3-coloring
Two greedy colorings of the same graph using different vertex orders. The right example generalizes to 2-colorable graphs with n vertices, where the greedy algorithm expends n/2 colors.
