| Article ID: | iaor1997985 |
| Country: | Netherlands |
| Volume: | 57 |
| Issue: | 2/3 |
| Start Page Number: | 93 |
| End Page Number: | 103 |
| Publication Date: | Feb 1995 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Annan J.D. |
| Keywords: | Tutte polynomial |
The complexity of calculating the coefficients of the Tutte polynomial of a graph is considered. The calculation of some coefficients is shown to be ¸ℝP-complete, whereas some other coefficients can be computed in polynomial time. However, even for a hard coefficient, it can be decided in polynomial time whether it is less than a fixed constant.