graph coloring
Sign in to saveAlso 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
- Commons category
- Graph coloring
- ACM Classification Code (2012)
- 10003639
- Stack Exchange tag
- cstheory.stackexchange.com/tags/graph-colouring
via Wikidata · CC0
~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.