Algorithms
| Graph coloring | |
| Decision | |
| 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 nn) |
| Complexity | NP-complete |
| Reduction from | 3-Satisfiability |
| Garey–Johnson | GT4 |
| Optimisation | |
| Name | Chromatic number |
| Input | Graph G with n vertices. |
| Output | χ(G) |
| Complexity | NP-hard |
| Approximability | O(n (log n)−3(log log n)2) |
| Inapproximability | O(n1−ε) unless P = NP |
| Counting problem | |
| Name | Chromatic polynomial |
| Input | Graph G with n vertices. Integer k |
| Output | The number P (G,k) of proper k-colorings of G |
| Running time | O(2 nn) |
| Complexity | #P-complete |
| Approximability | FPRAS for restricted cases |
| Inapproximability | No PTAS unless P = NP |
Read more about this topic: Graph Coloring