그래프 색칠
Sign in to saveAlso known as graph coloring problem, graph colouring
그래프의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법
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