グラフ彩色
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
- Instance of
- computational problem
- Subclass of
- graph labeling
- Image
- List-edge coloring (cb).svg
Show 7 more facts
- Commons category
- Graph coloring
- topic's main category
- Category:Graph coloring
- different from
- edge coloring
- ACM Classification Code (2012)
- 10003639
- computational complexity
- NP-complete
- maintained by WikiProject
- WikiProject Mathematics
- Stack Exchange tag
- cstheory.stackexchange.com/tags/graph-colouring
via Wikidata · CC0
Article · 日本語
グラフ彩色（英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色という。同様に辺彩色は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。
Abstract from DBpedia / Wikipedia · CC BY-SA