In graph theory, graph coloring is a special case of graph labeling, it is an assignment of labels traditionally called colors to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a such that no two adjacent vertices share the same color, this is called a vertex coloring. Vertex coloring is the point of the subject, and other coloring problems can be transformed into a vertex version. For example, a coloring of a graph is just a vertex coloring of its line graph. However, non-vertex coloring problems are often stated and studied as is and that is partly for perspective, and partly because some problems are best studied in non-vertex form, as for instance is edge coloring. The convention of using colors originates from coloring the countries of a map and this was generalized to coloring the faces of a graph embedded in the plane. By planar duality it became coloring the vertices, and in form it generalizes to all graphs. In mathematical and computer representations, it is typical to use the first few positive or nonnegative integers as the colors, in general, one can use any finite set as the color set. The nature of the coloring problem depends on the number of colors, graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned and it has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still an active field of research. Note, Many terms used in this article are defined in Glossary of graph theory, the first results about graph coloring deal almost exclusively with planar graphs in the form of the coloring of maps. Guthrie’s brother passed on the question to his mathematics teacher Augustus de Morgan at University College, arthur Cayley raised the problem at a meeting of the London Mathematical Society in 1879. The same year, Alfred Kempe published a paper that claimed to establish the result, for his accomplishment Kempe was elected a Fellow of the Royal Society and later President of the London Mathematical Society. In 1890, Heawood pointed out that Kempe’s argument was wrong, however, in that paper he proved the five color theorem, saying that every planar map can be colored with no more than five colors, using ideas of Kempe. The proof went back to the ideas of Heawood and Kempe, the proof of the four color theorem is also noteworthy for being the first major computer-aided proof. Kempe had already drawn attention to the general, non-planar case in 1879, the conjecture remained unresolved for 40 years, until it was established as the celebrated strong perfect graph theorem by Chudnovsky, Robertson, Seymour, and Thomas in 2002. One of the applications of graph coloring, register allocation in compilers, was introduced in 1981
All non-isomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph E3 (red) admits a 1-coloring, the others admit no such colorings. The green graph admits 12 colorings with 3 colors.
A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible.