การระบายสีกราฟ
Sign in to saveAlso known as graph coloring problem, graph colouring
assignment of colors to elements of a graph subject to certain constraints
In the Vinony graph
Vinony's link graph records 515 inbound references to การระบายสีกราฟ, and connects out to glossary of graph theory terms, four color theorem and graph theory.
It is catalogued under topics including Computational problems in graph theory, Extensions and generalizations of graphs and Graph coloring.
Vinony links it to 35 Wikipedia language editions.
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
Connections
glossary of graph theory terms
Entity
four color theorem
Entity
graph theory
Entity
graph
Entity
tree
Entity
planar graph
Entity
time complexity
Entity
cycle graph
Entity
clique
Entity
W. T. Tutte
Entity
chordal graph
Entity
polynomial-time approximation scheme
Entity
fractional coloring
Entity
United States
Country
International Standard Book Number
Entity
map
Entity
integer
Entity
pedagogy
Entity
computer program
Entity
Wayback Machine
Entity