Methodic assignment of colors to elements of a graph
Not to be confused with Edge coloring.
A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible.
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 graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.
Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is partly pedagogical, and partly because some problems are best studied in their non-vertex form, as in the case of edge coloring.
The convention of using colors originates from coloring the countries of a map, where each face is literally colored. This was generalized to coloring the faces of a graph embedded in the plane. By planar duality it became coloring the vertices, and in this form it generalizes to all graphs. In mathematical and computer representations, it is typical to use the first few positive or non-negative 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 but not on what they are.
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, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of research.
Note: Many terms used in this article are defined in Glossary of graph theory.
graph theory, graphcoloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject...
as is required in the graphcoloring problem. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after...
In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color...
of a graph is the maximum number of colors in a complete coloring. acyclic 1. A graph is acyclic if it has no cycles. An undirected acyclic graph is the...
registers representing available colors) would be a coloring for the original graph. As GraphColoring is an NP-Hard problem and Register Allocation is in...
colorings and cliques in those families. For instance, in all perfect graphs, the graphcoloring problem, maximum clique problem, and maximum independent set problem...
of graphcoloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed...
Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graphcoloring. In a...
The graphcoloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring...
vertex sets of two graphs that maps adjacent vertices to adjacent vertices. Homomorphisms generalize various notions of graphcolorings and allow the expression...
to be the smallest bridgeless cubic graph with no three-edge-coloring. Although the graph is generally credited to Petersen, it had in fact first appeared...
In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently...
In graph theory, a branch of mathematics, list coloring is a type of graphcoloring where each vertex can be restricted to a list of allowed colors. It...
"Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs", Metody Diskretnogo Analiza (41): 12–26, 108...
graph theory, total coloring is a type of graphcoloring on the vertices and edges of a graph. When used without any qualification, a total coloring is...
complete bipartite graph Km,n has a maximum matching of size min{m,n}. A complete bipartite graph Kn,n has a proper n-edge-coloring corresponding to a...
graph of the intervals. Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graphcoloring or...
person's job title is Colorist Graphcoloring, in mathematics Hair coloring Food coloring Hand-colouring of photographs Map coloring Color code (disambiguation)...
book graph K1,7 × K2 provides an example of a graph that is not harmonious. A graphcoloring is a subclass of graph labelings. Vertex colorings assign...
perfect graphs. They may be recognized in linear time, and several problems that are hard on other classes of graphs such as graphcoloring may be solved...
In complex analysis, domain coloring or a color wheel graph is a technique for visualizing complex functions by assigning a color to each point of the...
the resolution of extremal graph theory problems. A proper (vertex) coloring of a graph G {\displaystyle G} is a coloring of the vertices of G {\displaystyle...
border. The problem is then translated into a graphcoloring problem: one has to paint the vertices of the graph so that no edge has endpoints of the same...
Global Information