{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:09:49Z","timestamp":1773479389596,"version":"3.50.1"},"reference-count":84,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2007,7,6]],"date-time":"2007-07-06T00:00:00Z","timestamp":1183680000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,12]]},"DOI":"10.1007\/s00224-007-9022-9","type":"journal-article","created":{"date-parts":[[2007,7,5]],"date-time":"2007-07-05T15:38:45Z","timestamp":1183649925000},"page":"542-562","source":"Crossref","is-referenced-by-count":35,"title":["From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials"],"prefix":"10.1007","volume":"43","author":[{"given":"J. A.","family":"Makowsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,7,6]]},"reference":[{"key":"9022_CR1","series-title":"London Mathematical Society Lecture Note Series","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1017\/CBO9780511721328.004","volume-title":"Surveys in Combinatorics, 2001 (Sussex)","author":"M. Aigner","year":"2001","unstructured":"Aigner, M.: The Penrose polynomial of graphs and matroids. In: Surveys in Combinatorics, 2001 (Sussex). London Mathematical Society Lecture Note Series, vol.\u00a0288, pp.\u00a011\u201346. Cambridge University Press, Cambridge (2001)"},{"key":"9022_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.laa.2003.06.010","volume":"377","author":"M. Aigner","year":"2004","unstructured":"Aigner, M., van der Holst, H.: Interlace polynomials. Linear Algebra Appl. 377, 11\u201330 (2004)","journal-title":"Linear Algebra Appl."},{"key":"9022_CR3","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01204715","volume":"12","author":"N. Alon","year":"1992","unstructured":"Alon, N., Tarsi, M.: Colorings and orientations of graphs. Combinatorica 12, 125\u2013134 (1992)","journal-title":"Combinatorica"},{"key":"9022_CR4","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0012-365X(98)00113-7","volume":"190","author":"A. Andrzejak","year":"1998","unstructured":"Andrzejak, A.: An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discret. Math. 190, 39\u201354 (1998)","journal-title":"Discret. Math."},{"key":"9022_CR5","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.jctb.2004.03.003","volume":"92","author":"R. Arratia","year":"2004","unstructured":"Arratia, R., Bollob\u00e1s, B., Sorkin, G.B.: The interlace polynomial: a new graph polynomial. J. Comb. Theory Ser. B 92, 199\u2013233 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"9022_CR6","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/s00493-004-0035-6","volume":"24","author":"R. Arratia","year":"2004","unstructured":"Arratia, R., Bollob\u00e1s, B., Sorkin, G.B.: A two-variable interlace polynomial. Combinatorica 24(4), 567\u2013584 (2004)","journal-title":"Combinatorica"},{"key":"9022_CR7","unstructured":"Averbouch, I., Makowsky, J.A.: The complexity of multivariate matching polynomials. Preprint (January 2007). Available at www.cs.technion.ac.il\/admlogic\/TR\/readme.html"},{"key":"9022_CR8","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(86)90014-4","volume":"15","author":"D. Babi\u0107","year":"1986","unstructured":"Babi\u0107, D., Graovac, A., Mohar, B., Pisanski, T.: The matching polynomial of a polygraph. Discret. Appl. Math. 15, 11\u201324 (1986)","journal-title":"Discret. Appl. Math."},{"key":"9022_CR9","doi-asserted-by":"crossref","first-page":"42","DOI":"10.2307\/1967597","volume":"14","author":"G.D. Birkhoff","year":"1912","unstructured":"Birkhoff, G.D.: A determinant formula for the number of ways of coloring a map. Ann. Math. 14, 42\u201346 (1912)","journal-title":"Ann. Math."},{"key":"9022_CR10","unstructured":"Bl\u00e4ser, M., Dell, H.: Complexity of the cover polynomial. In: Proceedings of ICALP 2007. Lecture Notes in Computer Science. Springer (2007, to appear)"},{"key":"9022_CR11","unstructured":"Bl\u00e4ser, M., Dell, H., Makowsky, J.A.: Algebraic reductions for evaluations of the colored Tutte polynomial. Preprint (January 2007). Available at www.cs.technion.ac.il\/admlogic\/TR\/readme.html"},{"key":"9022_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers. Bull. Am. Math. Soc. 21, 1\u201346 (1989)","journal-title":"Bull. Am. Math. Soc."},{"key":"9022_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, New York (1998)"},{"key":"9022_CR14","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1999","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, New York (1999)"},{"key":"9022_CR15","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1017\/S0963548398003447","volume":"8","author":"B. Bollob\u00e1s","year":"1999","unstructured":"Bollob\u00e1s, B., Riordan, O.: A Tutte polynomial for coloured graphs. Comb. Probab. Comput. 8, 45\u201394 (1999)","journal-title":"Comb. Probab. Comput."},{"key":"9022_CR16","first-page":"73","volume":"3","author":"P. B\u00fcrgisser","year":"1999","unstructured":"B\u00fcrgisser, P.: On the structure of Valiant\u2019s complexity classes. Discret. Math. Theoret. Comput. Sci. 3, 73\u201394 (1999)","journal-title":"Discret. Math. Theoret. Comput. Sci."},{"key":"9022_CR17","series-title":"Algorithms and Computations in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04179-6","volume-title":"Completeness and Reduction in Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"2000","unstructured":"B\u00fcrgisser, P.: Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computations in Mathematics, vol.\u00a07. Springer, New York (2000)"},{"key":"9022_CR18","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1006\/aima.1996.0018","volume":"118","author":"T.Y. Chow","year":"1996","unstructured":"Chow, T.Y.: The path-cycle symmetric function of a digraph. Adv. Math. 118, 71\u201398 (1996)","journal-title":"Adv. Math."},{"issue":"2","key":"9022_CR19","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1006\/jctb.1995.1055","volume":"65","author":"F.R.K. Chung","year":"1995","unstructured":"Chung, F.R.K., Graham, R.L.: On the cover polynomial of a digraph. J. Comb. Theory Ser. B 65(2), 273\u2013290 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9022_CR20","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1051\/ita\/1992260302571","volume":"26","author":"B. Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second-order logic of graphs III: treewidth, forbidden minors and complexity issues. Inf. Theor. 26, 257\u2013286 (1992)","journal-title":"Inf. Theor."},{"key":"9022_CR21","series-title":"Foundations","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1142\/9789812384720_0005","volume-title":"Handbook of Graph Grammars and Computing by Graph Transformations","author":"B. Courcelle","year":"1997","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformations. Foundations, vol.\u00a01, pp. 313\u2013400. World Scientific, Singapore (1997), Chapter\u00a05"},{"key":"9022_CR22","unstructured":"Courcelle, B.: A multivariate interlace polynomial. Preprint arXiv cs\/0702016 (January 2007). Available at http:\/\/front.math.ucdavis.edu\/0702.6016"},{"key":"9022_CR23","unstructured":"Courcelle, B., Makowsky, J.A.: Recursive definitions of graph polynomials. Draft manuscript (2006)"},{"issue":"1\u20132","key":"9022_CR24","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic. Discret. Appl. Math. 108(1\u20132), 23\u201352 (2001)","journal-title":"Discret. Appl. Math."},{"key":"9022_CR25","unstructured":"Courcelle, B., Godlin, B., Makowsky, J.A.: Towards a theory of graph polynomials, I: second order definable polynomials (2007, in preparation)"},{"key":"9022_CR26","unstructured":"Cvetkovi\u0107, D.M., Doob, M., Sachs, H.: Spectra of Graphs, 3rd edn. Johann Ambrosius Barth (1995)"},{"key":"9022_CR27","volume-title":"Handbook of Theoretical Computer Science","author":"N. Dershowitz","year":"1990","unstructured":"Dershowitz, N., Jouannaud, J.-P.: Rewrite systems. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol.\u00a0B. Elsevier, Amsterdam (1990), Chapter\u00a06"},{"key":"9022_CR28","doi-asserted-by":"crossref","DOI":"10.1142\/5814","volume-title":"Chromatic Polynomials and Chromaticity of Graphs","author":"F.M. Dong","year":"2005","unstructured":"Dong, F.M., Koh, K.M., Teo, K.L.: Chromatic Polynomials and Chromaticity of Graphs. World Scientific, Singapore (2005)"},{"key":"9022_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parametrized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.F.: Parametrized Complexity. Springer, New York (1999)"},{"issue":"3\u20134","key":"9022_CR30","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"M. Dyer","year":"2000","unstructured":"Dyer, M., Greenhill, C.: The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3\u20134), 260\u2013289 (2000)","journal-title":"Random Struct. Algorithms"},{"key":"9022_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03182-7","volume-title":"Finite Model Theory. Perspectives in Mathematical Logic","author":"H.D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Perspectives in Mathematical Logic. Springer, New York (1995)"},{"key":"9022_CR32","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1006\/jctb.1998.1853","volume":"74","author":"J. Ellis-Monaghan","year":"1998","unstructured":"Ellis-Monaghan, J.: New results for the Martin polynomial. J. Comb. Theory Ser.\u00a0B 74, 326\u2013352 (1998)","journal-title":"J. Comb. Theory Ser.\u00a0B"},{"key":"9022_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(02)00831-9","volume":"306","author":"G.E. Farr","year":"2003","unstructured":"Farr, G.E.: The Go polynomials of a graph. Theor. Comput. Sci. 306, 1\u201318 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9022_CR34","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0095-8956(79)90049-2","volume":"26","author":"E.J. Farrell","year":"1979","unstructured":"Farrell, E.J.: On a general class of graph polynomials. J. Comb. Theory Ser.\u00a0B 26, 111\u2013122 (1979)","journal-title":"J. Comb. Theory Ser.\u00a0B"},{"key":"9022_CR35","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0012-365X(90)90202-S","volume":"82","author":"D.C. Fisher","year":"1990","unstructured":"Fisher, D.C., Solow, A.E.: Dependence polynomials. Discret. Math. 82, 251\u2013258 (1990)","journal-title":"Discret. Math."},{"key":"9022_CR36","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, New York (2006)"},{"key":"9022_CR37","first-page":"159","volume-title":"IMA Volumes in Mathematics and Its Applications","author":"I. Gessel","year":"1989","unstructured":"Gessel, I.: Generalized rook polynomials and orthogonal polynomials. In: IMA Volumes in Mathematics and Its Applications, vol.\u00a018, pp. 159\u2013176. Springer, New York (1989)"},{"key":"9022_CR38","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory","author":"C. Godsil","year":"2001","unstructured":"Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics. Springer, New York (2001)"},{"key":"9022_CR39","volume-title":"Algebraic Combinatorics","author":"C.D. Godsil","year":"1993","unstructured":"Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall, London (1993)"},{"key":"9022_CR40","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1006\/inco.1997.2675","volume":"140","author":"E. Gr\u00e4del","year":"1998","unstructured":"Gr\u00e4del, E., Gurevich, Y.: Metafinite model theory. Inf. Comput. 140, 26\u201381 (1998)","journal-title":"Inf. Comput."},{"key":"9022_CR41","series-title":"Encyclopedia of Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511551574","volume-title":"Model Theory","author":"W. Hodges","year":"1993","unstructured":"Hodges, W.: Model Theory. Encyclopedia of Mathematics and Its Applications, vol.\u00a042. Cambridge University Press, Cambridge (1993)"},{"key":"9022_CR42","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0012-365X(94)90163-5","volume":"125","author":"C. Hoede","year":"1994","unstructured":"Hoede, C., Li, X.: Clique polynomials and independent set polynomials of graphs. Discret. Math. 125, 219\u2013228 (1994)","journal-title":"Discret. Math."},{"key":"9022_CR43","series-title":"Graduate Texts in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer, New York (1999)"},{"key":"9022_CR44","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1090\/S0002-9939-1988-0943099-0","volume":"103","author":"F. Jaeger","year":"1988","unstructured":"Jaeger, F.: Tutte polynomials and link polynomials. Proc. Am. Math. Soc. 103, 647\u2013654 (1988)","journal-title":"Proc. Am. Math. Soc."},{"key":"9022_CR45","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"F. Jaeger","year":"1990","unstructured":"Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Philos. Soc. 108, 35\u201353 (1990)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"9022_CR46","volume-title":"Handbook of Theoretical Computer Science, vol.\u00a01","author":"D.S. Johnson","year":"1990","unstructured":"Johnson, D.S.: A catalog of complexity classes. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol.\u00a01. Elsevier, Amsterdam (1990), Chapter\u00a02"},{"key":"9022_CR47","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0166-218X(89)90049-8","volume":"25","author":"L.H. Kauffman","year":"1989","unstructured":"Kauffman, L.H.: A Tutte polynomial for signed graphs. Discret. Appl. Math. 25, 105\u2013127 (1989)","journal-title":"Discret. Appl. Math."},{"key":"9022_CR48","first-page":"5","volume":"2","author":"I.A. Lavrov","year":"1962","unstructured":"Lavrov, I.A.: Effective inseparability of the set of identically true formulas and the set of formulas with finite counterexamples for certain elementary theories. Algebra i Logika 2, 5\u201318 (1962) (in Russian)","journal-title":"Algebra i Logika"},{"key":"9022_CR49","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer, New York (2004)"},{"key":"9022_CR50","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/0607036","volume":"7","author":"M. Linial","year":"1986","unstructured":"Linial, M.: Hard enumeration problems in geometry and combinatorics. SIAM J. Algebr. Discret. Methods 7, 331\u2013335 (1986)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"issue":"1\u20132","key":"9022_CR51","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0196-8858(03)00087-3","volume":"32","author":"M. Lotz","year":"2004","unstructured":"Lotz, M., Makowsky, J.A.: On the algebraic complexity of some families of coloured Tutte polynomials. Adv. Appl. Math. 32(1\u20132), 327\u2013349 (2004)","journal-title":"Adv. Appl. Math."},{"key":"9022_CR52","series-title":"Annals of Discrete Mathematics","volume-title":"Matching Theory","author":"L. Lovasz","year":"1986","unstructured":"Lovasz, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics, vol.\u00a029. North-Holland, Amsterdam (1986)"},{"key":"9022_CR53","unstructured":"Makowsky, J.A.: Colored Tutte polynomials and Kauffman brackets on graphs of bounded tree width. In: Proceedings of the 12th Symposium on Discrete Algorithms, pp.\u00a0487\u2013495. SIAM (2001)"},{"key":"9022_CR54","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"J.A. Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Ann. Pure Appl. Log. 126, 1\u20133 (2004)","journal-title":"Ann. Pure Appl. Log."},{"issue":"2","key":"9022_CR55","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1016\/j.dam.2004.01.016","volume":"145","author":"J.A. Makowsky","year":"2005","unstructured":"Makowsky, J.A.: Colored Tutte polynomials and Kauffman brackets on graphs of bounded tree width. Discret. Appl. Math. 145(2), 276\u2013290 (2005)","journal-title":"Discret. Appl. Math."},{"key":"9022_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1007\/11780342_35","volume-title":"Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, July 2006","author":"J.A. Makowsky","year":"2006","unstructured":"Makowsky, J.A.: From a zoo to a zoology: descriptive complexity for graph polynomials. In: Beckmann, A., Berger, U., L\u00f6we, B., Tucker, J.V. (eds.) Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, July 2006. Lecture Notes in Computer Science, vol.\u00a03988, pp.\u00a0330\u2013341. Springer, New York (2006)"},{"key":"9022_CR57","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/S0196-8858(02)00530-4","volume":"30","author":"J.A. Makowsky","year":"2003","unstructured":"Makowsky, J.A., Mari\u00f1o, J.P.: Farrell polynomials on graphs of bounded treewidth. Adv. Appl. Math. 30, 160\u2013176 (2003)","journal-title":"Adv. Appl. Math."},{"issue":"4","key":"9022_CR58","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1016\/S0022-0000(03)00080-1","volume":"64","author":"J.A. Makowsky","year":"2003","unstructured":"Makowsky, J.A., Mari\u00f1o, J.P.: The parametrized complexity of knot polynomials. J. Comput. Syst. Sci. 64(4), 742\u2013756 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9022_CR59","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/3-540-44622-2_27","volume-title":"CSL\u201900","author":"J.A. Makowsky","year":"2000","unstructured":"Makowsky, J.A., Meer, K.: On the complexity of combinatorial and metafinite generating functions of graph properties in the computational model of Blum, Shub and Smale. In: CSL\u201900. Lecture Notes in Computer Science, vol.\u00a01862, pp.\u00a0399\u2013410. Springer, New York (2000)"},{"key":"9022_CR60","unstructured":"Makowsky, J.A., Zilber, B.: Polynomial invariants of graphs and totally categorical theories. MODNET Preprint no.\u00a021 (2006). Available at http:\/\/www.logique.jussieu.fr\/modnet\/Home\/index.hph"},{"key":"9022_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/11917496_18","volume-title":"Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22-23, 2006, Revised Papers","author":"J.A. Makowsky","year":"2006","unstructured":"Makowsky, J.A., Rotics, U., Averbouch, I., Godlin, B.: Computing graph polynomials on graphs of bounded clique-width. In: Fomin, F.V. (ed.) Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22-23, 2006, Revised Papers. Lecture Notes in Computer Science, vol.\u00a04271, pp.\u00a0191\u2013204. Springer, New York (2006)"},{"issue":"1\u20132","key":"9022_CR62","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0304-3975(98)00190-X","volume":"242","author":"K. Meer","year":"2000","unstructured":"Meer, K.: Counting problems over the reals. Theor. Comput. Sci. 242(1\u20132), 41\u201358 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9022_CR63","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1017\/S0963548398003551","volume":"7","author":"S.D. Noble","year":"1998","unstructured":"Noble, S.D.: Evaluating the Tutte polynomial for graphs of bounded tree-width. Comb. Probab. Comput. 7, 307\u2013321 (1998)","journal-title":"Comb. Probab. Comput."},{"key":"9022_CR64","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-21676-7","volume-title":"Bounded Variable Logics and Counting\u2014A Study in Finite Models","author":"M. Otto","year":"1997","unstructured":"Otto, M.: Bounded Variable Logics and Counting\u2014A Study in Finite Models, vol.\u00a09. Springer, New York (1997), IX+183 pages"},{"key":"9022_CR65","doi-asserted-by":"crossref","unstructured":"Oum, S.: Approximating rank-width and clique-width quickly. In: Graph Theoretic Concepts in Computer Science, WG 2005. Lecture Notes in Computer Science, vol.\u00a03787, pp.\u00a049\u201358 (2005)","DOI":"10.1007\/11604686_5"},{"key":"9022_CR66","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0012-365X(92)90289-R","volume":"109","author":"J.G. Oxley","year":"1992","unstructured":"Oxley, J.G., Welsh, D.J.A.: Tutte polynomials computable in polynomial time. Discret. Math. 109, 185\u2013192 (1992)","journal-title":"Discret. Math."},{"key":"9022_CR67","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"9022_CR68","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J. Petersen","year":"1891","unstructured":"Petersen, J.: Die Theorie der regul\u00e4ren Graphen. Acta Math. 15, 193\u2013220 (1891)","journal-title":"Acta Math."},{"key":"9022_CR69","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s00373-003-0544-x","volume":"20","author":"P. Pitteloud","year":"2004","unstructured":"Pitteloud, P.: Chromatic polynomials and the symmetric group. Graphs Comb. 20, 131\u2013144 (2004)","journal-title":"Graphs Comb."},{"key":"9022_CR70","volume-title":"An Introduction to Combinatorial Analysis","author":"J. Riordan","year":"1958","unstructured":"Riordan, J.: An Introduction to Combinatorial Analysis. Wiley, New York (1958)"},{"key":"9022_CR71","doi-asserted-by":"crossref","unstructured":"Sokal, A.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In: Survey in Combinatorics, 2005. London Mathematical Society Lecture Notes, vol.\u00a0327, pp.\u00a0173\u2013226 (2005)","DOI":"10.1017\/CBO9780511734885.009"},{"key":"9022_CR72","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0012-365X(73)90108-8","volume":"5","author":"R.P. Stanley","year":"1973","unstructured":"Stanley, R.P.: Acyclic orientations of graphs. Discret. Math. 5, 171\u2013178 (1973)","journal-title":"Discret. Math."},{"key":"9022_CR73","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1006\/aima.1995.1020","volume":"111","author":"R.P. Stanley","year":"1995","unstructured":"Stanley, R.P.: A symmetric function generalization of the chromatic polynomial of a graph. Adv. Math. 111, 166\u2013194 (1995)","journal-title":"Adv. Math."},{"key":"9022_CR74","first-page":"161","volume":"1","author":"J.J. Sylvester","year":"1878","unstructured":"Sylvester, J.J.: On an application of the new atomic theory to the graphical presentation of the invariants and covariants of binary quantics, with three appendices. Am. J. Math. 1, 161\u2013228 (1878)","journal-title":"Am. J. Math."},{"key":"9022_CR75","first-page":"24","volume":"1","author":"M.A. Taitslin","year":"1961","unstructured":"Taitslin, M.A.: Effective inseparability of the sets of identically true and finitely refutable formulae of elementary lattice theory. Algebra i Logika 1, 24\u201338 (1961) (in Russian)","journal-title":"Algebra i Logika"},{"issue":"2","key":"9022_CR76","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"21","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 21(2), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"key":"9022_CR77","volume-title":"Chemical Graph Theory","author":"N. Trinajsti\u0107","year":"1992","unstructured":"Trinajsti\u0107, N.: Chemical Graph Theory, 2nd edn. CRC Press, Boca Raton (1992)","edition":"2"},{"key":"9022_CR78","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/S0196-8858(03)00041-1","volume":"32","author":"W.T. Tutte","year":"2004","unstructured":"Tutte, W.T.: Graph-polynomials. Adv. Appl. Math. 32, 5\u20139 (2004)","journal-title":"Adv. Appl. Math."},{"key":"9022_CR79","doi-asserted-by":"crossref","first-page":"161","DOI":"10.7151\/dmgt.1049","volume":"17.2","author":"Z. Tuza","year":"1997","unstructured":"Tuza, Z.: Graph colorings with local constraints\u2014a survey. Discuss. Math.\u2014Graph Theory 17.2, 161\u2013228 (1997)","journal-title":"Discuss. Math.\u2014Graph Theory"},{"key":"9022_CR80","unstructured":"Valiant, L.: Reducibility by algebraic projections. In: Logic and Arithmetic: An International Symposium held in honour of Ernst Specker. L\u2019enseignement Math\u00e9matique, vol.\u00a030, pp.\u00a0365\u2013380. Universit\u00e9 de Gen\u00e8ve (1982)"},{"key":"9022_CR81","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proceedings of 11th STOC, pp.\u00a0249\u2013261 (1979)","DOI":"10.1145\/800135.804419"},{"issue":"3","key":"9022_CR82","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"9022_CR83","doi-asserted-by":"crossref","unstructured":"Voloshin, V.I.: Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. Fields Institute Monographs, vol.\u00a017. American Mathematical Society (2002)","DOI":"10.1090\/fim\/017"},{"key":"9022_CR84","series-title":"London Mathematical Society Lecture Notes Series","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511752506","volume-title":"Complexity: Knots, Colourings and Counting","author":"D.J.A. Welsh","year":"1993","unstructured":"Welsh, D.J.A.: Complexity: Knots, Colourings and Counting. London Mathematical Society Lecture Notes Series, vol.\u00a0186. Cambridge University Press, Cambridge (1993)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9022-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9022-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9022-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:34Z","timestamp":1558684294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9022-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,6]]},"references-count":84,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["9022"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9022-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,6]]}}}