coloration de graphe
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 · Français
En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l'allocation de registres en compilation.
Abstract from DBpedia / Wikipedia · CC BY-SA