Algorithms
| Chromatic polynomial | |
| Input | Graph with vertices. |
| Output | Coefficients of |
| Running time | for some constant |
| Complexity | #P-hard |
| Reduction from | #3SAT |
| #k-colorings | |
| Input | Graph with vertices. |
| Output | |
| Running time | In P for . for . Otherwise for some constant |
| Complexity | #P-hard unless |
| Approximability | No FPRAS for |
Computational problems associated with the chromatic polynomial include
- finding the chromatic polynomial of a given graph, for example finding its coefficients
- evaluating at a fixed point for given . When is a natural number, this problem is normally viewed as computing the number of -colorings of a given graph. For example, this includes the problem #3-coloring of counting the number of 3-colorings, a canonical problem in the study of complexity of counting, complete for the counting class #P.
The first problem is more general because if we knew the coefficients of we could evaluate it at any point in polynomial time because the degree is . The difficulty of the second type of problem depends strongly on the value of and has been intensively studied in computational complexity.
Read more about this topic: Chromatic Polynomial
Related Phrases
Related Words