**Coloring**

A number of interesting problems and applications can be explored by experimenting with ways to color either the edges or the vertices of a graph. When the problem or application involves coloring the vertices of a graph, the choice and
arrangment of the colors is called a *vertex-coloring*. An *edge-coloring* of a graph refers to the choice and arrangement of colors for the edges.

An edge-colored graph | A vertex-colored graph |

The minimum number of colors required for a vertex coloring with no adjacent vertices colored the same color is called the* vertex-chromatic number* or simply the *chromatic number* of the graph. The *edge-chromatic number* is the minimum number of colors that are required for an edge coloring with no adjacent edges colored the same color.

A graph with edge-chromatic number 8 and vertex-chromatic number 3.

An historically important theorem about finding the vertex-chromatic number
of a graph grew out of the *Four-color conjecture,* which claims that
every planar graph can be vertex-colored with four or fewer colors.

Copyright © 1999-2000 SciMathMN