graph coloring

Also known as graph coloring problem, graph colouring

assignment of colors to elements of a graph subject to certain constraints

Key facts

Name: Graph coloring, vertex coloring, k -coloring
Input: Graph G with n vertices. Integer k
Output: Does G admit a proper vertex coloring with k colors?
Running time: O (2 n )
Complexity: NP-complete
Reduction from: 3-Satisfiability
Garey johnson: GT4
Approximability: O ( n (log n ) (log log n ) )
Inapproximability: O ( n ) unless P = NP

via Wikipedia infobox

Wikidata facts

Image: List-edge coloring (cb).svg

Show 3 more facts

~40 min read

Article

A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible.

In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring is a special case of graph labeling. 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.