{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T06:26:45Z","timestamp":1771050405187,"version":"3.50.1"},"publisher-location":"Boston","reference-count":118,"publisher":"Birkh\u00e4user Boston","isbn-type":[{"value":"9780817647889","type":"print"},{"value":"9780817647896","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,9,16]],"date-time":"2010-09-16T00:00:00Z","timestamp":1284595200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2010,9,16]],"date-time":"2010-09-16T00:00:00Z","timestamp":1284595200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-0-8176-4789-6_9","type":"book-chapter","created":{"date-parts":[[2010,10,14]],"date-time":"2010-10-14T07:42:50Z","timestamp":1287042170000},"page":"219-255","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["Graph Polynomials and Their Applications I: The Tutte Polynomial"],"prefix":"10.1007","author":[{"given":"Joanna A.","family":"Ellis-Monaghan","sequence":"first","affiliation":[]},{"given":"Criel","family":"Merino","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,9,16]]},"reference":[{"key":"9_CR1_9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04315-8","volume-title":"Proofs from the book","author":"M Aigner","year":"2001","unstructured":"Aigner M, Ziegler GM (2001) Proofs from the book. Springer, Berlin, Heidelberg"},{"key":"9_CR2_9","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/rsa.3240060409","volume":"6","author":"N Alon","year":"1995","unstructured":"Alon N, Frieze AM, Welsh DJA (1995) Polynomial time randomized approximation schemes for Tutte\u2013Gr\u00f6thendieck invariants: the dense case. Random Struct Algorithm 6:459\u2013478","journal-title":"Random Struct Algorithm"},{"key":"9_CR3_9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0012-365X(98)00113-7","volume":"190","author":"A Andrzejak","year":"1998","unstructured":"Andrzejak A (1998) An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discrete Math 190:39\u201354","journal-title":"Discrete Math"},{"key":"9_CR4_9","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1103\/PhysRevA.38.364","volume":"38","author":"P Bak","year":"1988","unstructured":"Bak P, Tang C, Wiesenfeld K (1988) Self-organized criticality. Phys Rev A 38:364\u2013374","journal-title":"Phys Rev A"},{"key":"9_CR5_9","first-page":"211","volume":"109","author":"J Benashski","year":"1995","unstructured":"Benashski J, Martin R, Moore J, Traldi L (1995) On the \u03b2-invariant for graphs. Congr Numer 109:211\u2013221","journal-title":"Congr Numer"},{"key":"9_CR6_9","volume-title":"Algebraic graph theory","author":"N Biggs","year":"1996","unstructured":"Biggs N (1996) Algebraic graph theory, 2nd edn. Cambridge University Press, Cambridge","edition":"2"},{"key":"9_CR7_9","volume-title":"Chip firing and the critical group of a graph","author":"N Biggs","year":"1996","unstructured":"Biggs N (1996) Chip firing and the critical group of a graph. Research report, London school of economics, London"},{"key":"9_CR8_9","doi-asserted-by":"publisher","first-page":"42","DOI":"10.2307\/1967597","volume":"14","author":"GD Birkhoff","year":"1912","unstructured":"Birkhoff GD (1912) A determinant formula for the number of ways of coloring a map. Ann Math 14:42\u201346","journal-title":"Ann Math"},{"key":"9_CR9_9","volume-title":"Matroid applications, encyclopedia of mathematics and its applications","author":"A Bj\u00f6rner","year":"1992","unstructured":"Bj\u00f6rner A (1992) Homology and shellability of matroids and geometric lattices. In: White N (ed) Matroid applications, encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge"},{"key":"9_CR10_9","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender HL (1993) A tourist guide through treewidth. Acta Cybernet 11:1\u201321","journal-title":"Acta Cybernet"},{"key":"9_CR11_9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern graph theory","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s B (1998) Modern graph theory. Graduate texts in mathematics. Springer, New York"},{"key":"9_CR12_9","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1017\/S0963548305006942","volume":"15","author":"C Borgs","year":"2006","unstructured":"Borgs C (2006) Absence of zeros for the chromatic polynomial on bounded degree graphs. Combinator Probab Comput 15:63\u201374","journal-title":"Combinator Probab Comput"},{"key":"9_CR13_9","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1006\/jctb.2001.2057","volume":"83","author":"JI Brown","year":"2001","unstructured":"Brown JI, Hickman CA, Sokal AD, Wagner DG (2001) On the chromatic roots of generalized theta graphs. J Combin Theory B 83:272\u2013297","journal-title":"J Combin Theory B"},{"key":"9_CR14_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0002-9947-1971-0288039-7","volume":"154","author":"T Brylawski","year":"1971","unstructured":"Brylawski T (1971) A combinatorial model for series\u2013parallel networks. Trans Am Math Soc 154:1\u201322","journal-title":"Trans Am Math Soc"},{"key":"9_CR15_9","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1090\/S0002-9947-1972-0309764-6","volume":"171","author":"T Brylawski","year":"1972","unstructured":"Brylawski T (1972) A decomposition for combinatorial geometries. Trans Am Math Soc 171:235\u2013282","journal-title":"Trans Am Math Soc"},{"key":"9_CR16_9","unstructured":"Brylawski T (1982) The Tutte polynomial, Part 1: general theory. In: Barlotti A (ed) Matroid theory and its applications. Proceedings of the 3rd international mathematical summer center (C.I.M.E. 1980)"},{"key":"9_CR17_9","volume-title":"Matroid applications, encyclopedia of mathematics and its applications","author":"T Brylawski","year":"1992","unstructured":"Brylawski T, Oxley J (1992) The Tutte polynomial and its applications. In: White N (ed) Matroid applications, encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge"},{"key":"9_CR18_9","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/S0378-4371(01)00142-X","volume":"296","author":"SC Chang","year":"2001","unstructured":"Chang SC, Shrock R (2001) Exact Potts model partition functions on wider arbitrary-length strips of the square lattice. Physica A 296:234\u2013288","journal-title":"Physica A"},{"key":"9_CR19_9","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1023\/B:JOSS.0000012508.58718.83","volume":"114","author":"SC Chang","year":"2004","unstructured":"Chang SC, Jacobsen J, Salas J, Shrock R (2004) Exact Potts model partition functions for strips of the triangular lattice. J Stat Phys 114:768\u2013823","journal-title":"J Stat Phys"},{"key":"9_CR20_9","first-page":"177","volume":"22","author":"MK Chari","year":"1997","unstructured":"Chari MK, Colbourn CJ (1997) Reliability polynomials: a survey. J Combin Inf System Sci 22:177\u2013193","journal-title":"J Combin Inf System Sci"},{"key":"9_CR21_9","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0012-365X(97)90031-5","volume":"172","author":"GL Chia","year":"1997","unstructured":"Chia GL (1997) A bibliography on chromatic polynomials. Discrete Math 172:175\u2013191","journal-title":"Discrete Math"},{"key":"9_CR22_9","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/S0196-8858(03)00078-2","volume":"32","author":"YB Choe","year":"2004","unstructured":"Choe YB, Oxley JG, Sokal AD, Wagner DG (2004) Homogeneous multivariate polynomials with the half-plane property. Adv Appl Math 32:88\u2013187","journal-title":"Adv Appl Math"},{"key":"9_CR23_9","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0021-9800(67)80051-6","volume":"2","author":"HH Crapo","year":"1967","unstructured":"Crapo HH (1967) A higher invariant for matroids. J Combin Theory 2:406\u2013417","journal-title":"J Combin Theory"},{"key":"9_CR24_9","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01817442","volume":"3","author":"HH Crapo","year":"1969","unstructured":"Crapo HH (1969) The Tutte polynomial. Aeq Math 3:211\u2013229","journal-title":"Aeq Math"},{"key":"9_CR25_9","doi-asserted-by":"publisher","first-page":"1613","DOI":"10.1103\/PhysRevLett.64.1613","volume":"64","author":"D Dhar","year":"1990","unstructured":"Dhar D (1990) Self-organized critical state of sandpile automaton models. Phys Rev Lett 64:1613\u20131616","journal-title":"Phys Rev Lett"},{"key":"9_CR26_9","volume-title":"Graph theory","author":"R Diestel","year":"2000","unstructured":"Diestel R (2000) Graph theory. Graduate texts in mathematics. Springer, New York"},{"key":"9_CR27_9","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.disc.2003.11.006","volume":"282","author":"FM Dong","year":"2004","unstructured":"Dong FM (2004) The largest non-integer zero of chromatic polynomials of graphs with fixed order. Discrete Math 282:103\u2013112","journal-title":"Discrete Math"},{"key":"9_CR28_9","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.disc.2003.12.005","volume":"282","author":"FM Dong","year":"2004","unstructured":"Dong FM, Koh KM (2004) On upper bounds for real roots of chromatic polynomials. Discrete Math 282:95\u2013101","journal-title":"Discrete Math"},{"key":"9_CR29_9","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/j.jctb.2006.07.005","volume":"97","author":"FM Dong","year":"2007","unstructured":"Dong FM, Koh KM (2007) Bounds for the coefficients of flow polynomials. J Combin Theory B 97:413\u2013420","journal-title":"J Combin Theory B"},{"key":"9_CR30_9","doi-asserted-by":"publisher","DOI":"10.1142\/9789812569462","volume-title":"Chromatic polynomials and chromaticity of graphs","author":"FM Dong","year":"2005","unstructured":"Dong FM, Koh KM, Teo KL (2005) Chromatic polynomials and chromaticity of graphs. World Scientific, Hackensack, NJ"},{"key":"9_CR31_9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"RJ Duffin","year":"1965","unstructured":"Duffin RJ (1965) Topology of series\u2013parallel networks. J Math Anal Appl 10:303\u2013318","journal-title":"J Math Anal Appl"},{"key":"9_CR32_9","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.disc.2003.10.018","volume":"281","author":"J Ellis-Monaghan","year":"2004","unstructured":"Ellis-Monaghan J (2004) Exploring the Tutte\u2013Martin connection. Discrete Math 281:173\u2013187","journal-title":"Discrete Math"},{"key":"9_CR33_9","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/S0196-8858(03)00079-4","volume":"32","author":"J Ellis-Monaghan","year":"2004","unstructured":"Ellis-Monaghan J (2004) Identities for the circuit partition polynomials, with applications to the diagonal Tutte polynomial. Adv Appl Math 32:188\u2013197","journal-title":"Adv Appl Math"},{"key":"9_CR34_9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0012-365X(95)00332-Q","volume":"179","author":"G Etienne","year":"1998","unstructured":"Etienne G, Las Vergnas M (1998) External and internal elements of a matroid basis. Discrete Math 179:111\u2013119","journal-title":"Discrete Math"},{"key":"9_CR35_9","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1017\/S0963548305007364","volume":"15","author":"GE Farr","year":"2006","unstructured":"Farr GE (2006) The complexity of counting colourings of subgraphs of the grid. Combinator Probab Comput 15:377\u2013383","journal-title":"Combinator Probab Comput"},{"key":"9_CR36_9","volume-title":"Combinatorics, complexity, and chance: a tribute to Dominic Welsh","author":"GE Farr","year":"2007","unstructured":"Farr GE (2007) Tutte\u2013Whitney polynomials: some history and generalizations. In: Grimmett GR, McDiarmid CJH (eds) Combinatorics, complexity, and chance: a tribute to Dominic Welsh. Oxford University Press, Oxford"},{"key":"9_CR37_9","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1017\/S0963548307008632","volume":"17","author":"R Fernandez","year":"2008","unstructured":"Fernandez R, Procacci A (2008) Regions without complex zeros for chromatic polynomials on graphs with bounded degree. Combinator Probab Comput 17:225\u2013238","journal-title":"Combinator Probab Comput"},{"key":"9_CR38_9","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0378-4371(93)90267-8","volume":"195","author":"A Gabrielov","year":"1993","unstructured":"Gabrielov A (1993) Abelian avalanches and the Tutte polynomials. Physica A 195:253\u2013274","journal-title":"Physica A"},{"key":"9_CR39_9","volume-title":"Computers and intractability \u2013 a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability \u2013 a guide to the theory of NP-completeness. W.H. Freeman, San Francisco"},{"key":"9_CR40_9","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1016\/j.ejc.2005.11.006","volume":"28","author":"E Gioan","year":"2007","unstructured":"Gioan E (2007) Enumerating degree sequences in digraphs and a cycle\u2013cocycle reversing system. Eur J Combinator 28:1351\u20131366","journal-title":"Eur J Combinator"},{"key":"9_CR41_9","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.disc.2005.04.010","volume":"298","author":"E Gioan","year":"2005","unstructured":"Gioan E, Las Vergnas M (2005) Activity preserving bijections between spanning trees and orientations in graphs. Discrete Math 298:169\u2013188","journal-title":"Discrete Math"},{"key":"9_CR42_9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10801-006-0035-2","volume":"25","author":"E Gioan","year":"2007","unstructured":"Gioan E, Las Vergnas M (2007) On the evaluation at (j, j\n                     2) of the Tutte polynomial of a ternary matroid. J Algebr Combinator 25:1\u20136","journal-title":"J Algebr Combinator"},{"key":"9_CR43_9","doi-asserted-by":"crossref","unstructured":"Goldberg LA, Jerrum MR (2007) Inapproximability of the Tutte polynomial. In STOC \u201907: Proceedings of the 39th annual ACM symposium on theory of computing. ACM Press, New York","DOI":"10.1145\/1250790.1250858"},{"key":"9_CR44_9","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1090\/S0002-9947-1983-0712251-1","volume":"280","author":"C Green","year":"1983","unstructured":"Green C, Zaslavsky T (1983) On the interpretation of whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions and orientations of graphs. Trans Am Math Soc 280:97\u2013126","journal-title":"Trans Am Math Soc"},{"key":"9_CR45_9","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1017\/S0963548300000705","volume":"2","author":"B Jackson","year":"1993","unstructured":"Jackson B (1993) A zero-free interval for chromatic polynomials of graphs. Combinator Probab Comput 2:325\u2013336","journal-title":"Combinator Probab Comput"},{"key":"9_CR46_9","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s00022-003-1694-y","volume":"76","author":"B Jackson","year":"2003","unstructured":"Jackson B (2003) Zeros of chromatic and flow polynomials of graphs. J Geom. 76:95\u2013109","journal-title":"J Geom."},{"key":"9_CR47_9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1017\/S0963548306007747","volume":"16","author":"B Jackson","year":"2007","unstructured":"Jackson B (2007) Zero-free intervals for flow polynomials of near-cubic graphs. Combinator Probab Comput 16:85\u2013108","journal-title":"Combinator Probab Comput"},{"key":"9_CR48_9","unstructured":"Jaeger F (1976) On nowhere-zero flows in multigraphs. In: Nash-Williams Crispin St JA, Sheehan J (eds) Proceedings of the 5th British combinatorial conference, Winnipeg"},{"key":"9_CR49_9","volume-title":"Selected topics in graph theory, vol 3","author":"F Jaeger","year":"1988","unstructured":"Jaeger F (1988) Nowhere-zero flow problems. In: Beineke LW, Wilson RJ (eds) Selected topics in graph theory, vol 3. Academic, New York"},{"key":"9_CR50_9","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"F Jaeger","year":"1990","unstructured":"Jaeger F, Vertigan DL, Welsh DJA (1990) On the computational complexity of the Jones and Tutte polynomials. Math Proc Cambridge Philos Soc 108:35\u201353","journal-title":"Math Proc Cambridge Philos Soc"},{"key":"9_CR51_9","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/0222066","volume":"22","author":"MR Jerrum","year":"1993","unstructured":"Jerrum MR, Sinclair A (1993) Polynomial time approximation algorithms for the Ising model. SIAM J Comput 22:1087\u20131116","journal-title":"SIAM J Comput"},{"key":"9_CR52_9","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1016\/0031-8914(61)90063-5","volume":"27","author":"PW Kasteleyn","year":"1961","unstructured":"Kasteleyn PW (1961) The statistics of dimers on a lattice. Physica 27:1209\u20131225","journal-title":"Physica"},{"key":"9_CR53_9","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579176","volume":"1","author":"DJ Kleitman","year":"1981","unstructured":"Kleitman DJ, Winston KJ (1981) Forests and score vectors. Combinatorica 1:49\u201354","journal-title":"Combinatorica"},{"key":"9_CR54_9","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1006\/jctb.1998.1888","volume":"76","author":"W Kook","year":"1999","unstructured":"Kook W, Reiner V, Stanton D (1999) A convolution formula for the Tutte polynomial. J Combin Theory B 76:297\u2013300","journal-title":"J Combin Theory B"},{"key":"9_CR55_9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0012-365X(77)90042-5","volume":"20","author":"M Las Vergnas","year":"1977","unstructured":"Las Vergnas M (1977) Acyclic and totally cyclic orientations of combinatorial geometries. Discrete Math 20:51\u201361","journal-title":"Discrete Math"},{"key":"9_CR56_9","volume-title":"Progress in graph theory, Proceedings of Waterloo Silver Jubilee Combinatorial Conference 1982","author":"M Las Vergnas","year":"1984","unstructured":"Las Vergnas M (1984) The Tutte polynomial of a morphism of matroids II. Activities of orientations. In: Bondy JA, Murty USR (eds) Progress in graph theory, Proceedings of Waterloo Silver Jubilee Combinatorial Conference 1982. Academic, Toronto"},{"key":"9_CR57_9","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0095-8956(88)90079-2","volume":"44","author":"M Las Vergnas","year":"1988","unstructured":"Las Vergnas M (1988) On the evaluation at (3,3) of the Tutte polynomial of a graph. J Combin Theory B 44:367\u2013372","journal-title":"J Combin Theory B"},{"key":"9_CR58_9","unstructured":"Las Vergnas M. The Tutte polynomial of a morphism of matroids V. Derivatives as generating functions, Preprint"},{"key":"9_CR59_9","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1103\/PhysRev.162.162","volume":"162","author":"EH Lieb","year":"1967","unstructured":"Lieb EH (1967) Residual entropy of square ice. Phys Rev 162:162\u2013172","journal-title":"Phys Rev"},{"key":"9_CR60_9","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/j.dam.2004.01.016","volume":"145","author":"JA Makowsky","year":"2005","unstructured":"Makowsky JA (2005) Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Appl Math 145:276\u2013290","journal-title":"Discrete Appl Math"},{"key":"9_CR61_9","doi-asserted-by":"crossref","unstructured":"Makowsky JA, Rotics U, Averbouch I, Godlin B (2006) Computing graph polynomials on graphs of bounded clique-width. In: Lecture Notes in Computer Science 4271. Springer, New York","DOI":"10.1007\/11917496_18"},{"key":"9_CR62_9","unstructured":"Martin P (1977) Enum\u00e9rations eul\u00e9riennes dans le multigraphs et invariants de Tutte\u2013Gr\u00f6thendieck. PhD thesis, Grenoble"},{"key":"9_CR63_9","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/0095-8956(78)90050-3","volume":"24","author":"P Martin","year":"1978","unstructured":"Martin P (1978) Remarkable valuation of the dichromatic polynomial of planar multigraphs. J Combin Theory B 24:318\u2013324","journal-title":"J Combin Theory B"},{"key":"9_CR64_9","first-page":"97","volume":"150","author":"TA McKee","year":"2001","unstructured":"McKee TA (2001) Recognizing dual-chordal graphs. Congr Numer 150:97\u2013103","journal-title":"Congr Numer"},{"key":"9_CR65_9","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF02558479","volume":"1","author":"C Merino","year":"1997","unstructured":"Merino C (1997) Chip firing and the Tutte polynomial. Ann Combin 1:253\u2013259","journal-title":"Ann Combin"},{"key":"9_CR66_9","doi-asserted-by":"crossref","unstructured":"Merino C (2001) The chip firing game and matroid complex. Discrete Mathematics and Theoretical Computer Science, Proceedings, vol AA, pp 245\u2013256","DOI":"10.46298\/dmtcs.2278"},{"key":"9_CR67_9","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1006\/jctb.2001.2058","volume":"83","author":"C Merino","year":"2001","unstructured":"Merino C, de Mier A, Noy M (2001) Irreducibility of the Tutte polynomial of a connected matroid. J Combin Theory B 83:298\u2013304","journal-title":"J Combin Theory B"},{"key":"9_CR68_9","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1017\/S0963548398003551","volume":"7","author":"SD Noble","year":"1998","unstructured":"Noble SD (1998) Evaluating the Tutte polynomial for graphs of bounded tree-width. Combinator Probab Comput 7:307\u2013321","journal-title":"Combinator Probab Comput"},{"key":"9_CR69_9","volume-title":"Combinatorics, complexity, and chance: a tribute to Dominic Welsh","author":"SD Noble","year":"2007","unstructured":"Noble SD (2007) The complexity of graph polynomials. In: Grimmett GR, McDiarmid CJH (eds) Combinatorics, complexity, and chance: a tribute to Dominic Welsh. Oxford University Press, Oxford"},{"key":"9_CR70_9","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum S, Seymour PD (2006) Approximating clique-width and branch-width. J Combin Theory B 96:514\u2013528","journal-title":"J Combin Theory B"},{"key":"9_CR71_9","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1002\/sapm1982663267","volume":"66","author":"J Oxley","year":"1982","unstructured":"Oxley J (1982) On Crapo\u2019s beta invariant for matroids. Stud Appl Math 66:267\u2013277","journal-title":"Stud Appl Math"},{"key":"9_CR72_9","volume-title":"Graph theory and related topics","author":"J Oxley","year":"1979","unstructured":"Oxley J, Welsh DJA (1979) The Tutte polynomial and percolation. In: Bondy JA, Murty USR (eds) Graph theory and related topics. Academic, London"},{"key":"9_CR73_9","doi-asserted-by":"publisher","first-page":"2680","DOI":"10.1021\/ja01315a102","volume":"57","author":"L Pauling","year":"1935","unstructured":"Pauling L (1935) The structure and entropy of ice and of other crystals with some randomness of atomic arrangement. J Am Chem Soc 57:2680\u20132684","journal-title":"J Am Chem Soc"},{"key":"9_CR74_9","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00220-002-0789-x","volume":"235","author":"A Procacci","year":"2003","unstructured":"Procacci A, Scoppola B, Gerasimov V (2003) Potts model on infinite graphs and the limit of chromatic polynomials. Commun Math Phys 235:215\u2013231","journal-title":"Commun Math Phys"},{"key":"9_CR75_9","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1287\/moor.5.4.576","volume":"5","author":"JS Provan","year":"1980","unstructured":"Provan JS, Billera LJ (1980) Decompositions of simplicial complexes related to diameters of convex polyhedra. Math Oper Res 5:576\u2013594","journal-title":"Math Oper Res"},{"key":"9_CR76_9","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/S0021-9800(68)80087-0","volume":"4","author":"RC Read","year":"1968","unstructured":"Read RC (1968) An introduction to chromatic polynomials. J Combin Theory B 4:52\u201371","journal-title":"J Combin Theory B"},{"key":"9_CR77_9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0167-5060(08)70508-9","volume":"3","author":"RC Read","year":"1978","unstructured":"Read RC, Rosenstiehl P (1978) On the principal edge tripartition of a graph. Ann Discrete Math 3:195\u2013226","journal-title":"Ann Discrete Math"},{"key":"9_CR78_9","volume-title":"Graph theory, combinatorics, and applications","author":"RC Read","year":"1991","unstructured":"Read RC, Royle G (1991) Chromatic roots of families of graphs. In: Alavi Y et al (eds) Graph theory, combinatorics, and applications. Wiley, New York"},{"key":"9_CR79_9","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1984","unstructured":"Robertson N, Seymour PD (1984) Graph minors. I. Excluding a forest. J Combin Theory B 35:39\u201361","journal-title":"I. Excluding a forest. J Combin Theory B"},{"key":"9_CR80_9","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson N, Seymour PD (1984) Graph minors. III. Planar tree-width. J Combin Theory B 36:49\u201364","journal-title":"III. Planar tree-width. J Combin Theory B"},{"key":"9_CR81_9","first-page":"309","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson N, Seymour PD (1986) Graph minors. II. Algorithmic aspects of tree-width. J Algorithm 7:309\u2013322","journal-title":"II. Algorithmic aspects of tree-width. J Algorithm"},{"issue":"1","key":"9_CR82_9","doi-asserted-by":"crossref","first-page":"N18","DOI":"10.37236\/1019","volume":"14","author":"G Royle","year":"2007","unstructured":"Royle G (2007) Graphs with chromatic roots in the interval (1,2). Electron J Combinator 14(1):N18","journal-title":"Electron J Combinator"},{"key":"9_CR83_9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s00026-008-0347-0","volume":"12","author":"G Royle","year":"2008","unstructured":"Royle G (2008) Planar triangulations with real chromatic roots arbitrarily close to four. Ann Combinator 12:195\u2013210","journal-title":"Ann Combinator"},{"key":"9_CR84_9","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1006\/jctb.1993.1040","volume":"58","author":"W Schw\u00e4rzler","year":"1993","unstructured":"Schw\u00e4rzler W (1993) The coefficients of the Tutte polynomial are not unimodal. J Combin Theory B 58:240\u2013242","journal-title":"J Combin Theory B"},{"key":"9_CR85_9","volume-title":"Computing the Tutte polynomial of a graph of moderate size","author":"K Sekine","year":"1995","unstructured":"Sekine K, Imai H, Tani S (1995) Computing the Tutte polynomial of a graph of moderate size. In: Lecture Notes in Computer Science. Springer, Berlin"},{"key":"9_CR86_9","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0095-8956(81)90058-7","volume":"30","author":"PD Seymour","year":"1981","unstructured":"Seymour PD (1981) Nowhere-zero 6-flows. J Combin Theory B, 30, 130\u2013135","journal-title":"J Combin Theory B"},{"key":"9_CR87_9","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1017\/S0305004100051306","volume":"77","author":"PD Seymour","year":"1975","unstructured":"Seymour PD, Welsh DJA (1975) Combinatorial applications of an inequality of statistical mechanics. Math Proc Cambridge Philos Soc 77:485\u2013495","journal-title":"Math Proc Cambridge Philos Soc"},{"key":"9_CR88_9","doi-asserted-by":"publisher","first-page":"5165","DOI":"10.1103\/PhysRevE.55.5165","volume":"55","author":"R Shrock","year":"1997","unstructured":"Shrock R, Tsai SH (1997) Asymptotic limits and zeros of chromatic polynomials and ground state entropy of Potts antiferromagnets. Phys Rev E 55:5165\u20135179","journal-title":"Phys Rev E"},{"key":"9_CR89_9","doi-asserted-by":"publisher","first-page":"3935","DOI":"10.1103\/PhysRevE.56.3935","volume":"56","author":"R Shrock","year":"1997","unstructured":"Shrock R, Tsai SH (1997) Families of graphs with W\n                     \n                r\n              (G, q) functions that are nonanalytic at \n$$1\/q = 0$$\n. Phys Rev E 56:3935\u20133943","journal-title":"Phys Rev E"},{"key":"9_CR90_9","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0378-4371(98)00359-8","volume":"259","author":"R Shrock","year":"1998","unstructured":"Shrock R, Tsai SH (1998) Ground state entropy of Potts antiferromagnets: cases with noncompact W boundaries having multiple points at \n$$1\/q = 0$$\n. Physica A 259:315\u2013348","journal-title":"Physica A"},{"key":"9_CR91_9","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1016\/S0012-365X(00)00336-8","volume":"231","author":"R Shrock","year":"2001","unstructured":"Shrock R (2001) Chromatic polynomials and their zeros and asymptotic limits for families of graphs. Discrete Math 231:421\u2013446","journal-title":"Discrete Math"},{"key":"9_CR92_9","first-page":"21","volume":"7","author":"AD Sokal","year":"2001","unstructured":"Sokal AD (2001) A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models. Markov Process Relat Fields 7:21\u201338","journal-title":"Markov Process Relat Fields"},{"key":"9_CR93_9","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1017\/S0963548300004612","volume":"10","author":"AD Sokal","year":"2001","unstructured":"Sokal AD (2001) Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combinator Probab Comput 10:41\u201377","journal-title":"Combinator Probab Comput"},{"key":"9_CR94_9","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1017\/S0963548303006023","volume":"13","author":"AD Sokal","year":"2004","unstructured":"Sokal AD (2004) Chromatic roots are dense in the whole complex plane. Combinator Probab Comput 13:221\u2013261","journal-title":"Combinator Probab Comput"},{"key":"9_CR95_9","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0012-365X(73)90108-8","volume":"5","author":"R Stanley","year":"1973","unstructured":"Stanley R (1973) Acyclic orientations of graphs. Discrete Math 5:171\u2013178","journal-title":"Discrete Math"},{"key":"9_CR96_9","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0167-5060(08)70717-9","volume":"6","author":"R Stanley","year":"1980","unstructured":"Stanley R (1980) Decomposition of rational polytopes. Ann Discrete Math 6:333\u2013342","journal-title":"Ann Discrete Math"},{"key":"9_CR97_9","unstructured":"Stanley R (1996) Combinatorics and commutative algebra, 2nd edn. Progress in Mathematics, vol 41. Birkh\u00e4user, Boston Besel Stuttgart"},{"key":"9_CR98_9","volume-title":"Enumerative combinatorics","author":"R Stanley","year":"1996","unstructured":"Stanley R (1996) Enumerative combinatorics, vol 1. Cambridge University Press, Cambridge"},{"key":"9_CR99_9","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511609589","volume-title":"Enumerative combinatorics","author":"R Stanley","year":"1999","unstructured":"Stanley R (1999) Enumerative combinatorics, vol 2. Cambridge University Press, Cambridge"},{"key":"9_CR100_9","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1017\/S0963548397003131","volume":"6","author":"C Thomassen","year":"1997","unstructured":"Thomassen C (1997) The zero-free intervals for chromatic polynomials of graphs. Combinator Probab Comput 6:497\u2013506","journal-title":"Combinator Probab Comput"},{"key":"9_CR101_9","doi-asserted-by":"publisher","first-page":"1032","DOI":"10.1016\/j.dam.2005.09.013","volume":"154","author":"L Traldi","year":"2006","unstructured":"Traldi L (2006) On the colored Tutte polynomial of a graph of bounded treewidth. Discrete Appl Math 154:1032\u20131036","journal-title":"Discrete Appl Math"},{"key":"9_CR102_9","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1017\/S0305004100023173","volume":"43","author":"WT Tutte","year":"1947","unstructured":"Tutte WT (1947) A ring in graph theory. Proc Cambridge Philos Soc 43:26\u201340","journal-title":"Proc Cambridge Philos Soc"},{"key":"9_CR103_9","unstructured":"Tutte WT (1948) An algebraic theory of graphs, PhD thesis, University of Cambridge"},{"key":"9_CR104_9","doi-asserted-by":"crossref","first-page":"80","DOI":"10.4153\/CJM-1954-010-9","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte WT (1954) A contribution to the theory of chromatic polynomials. Can J Math 6:80\u201391","journal-title":"Can J Math"},{"key":"9_CR105_9","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0021-9800(67)80032-2","volume":"2","author":"WT Tutte","year":"1967","unstructured":"Tutte WT (1967) On dichromatic polynomials. J Combin Theory 2:301\u2013320","journal-title":"J Combin Theory"},{"key":"9_CR106_9","volume-title":"Graph theory","author":"WT Tutte","year":"1984","unstructured":"Tutte WT (1984) Graph theory. Cambridge University Press, Cambridge"},{"key":"9_CR107_9","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/S0196-8858(03)00041-1","volume":"32","author":"WT Tutte","year":"2004","unstructured":"Tutte WT (2004) Graph-polynomials. Special issue on the Tutte polynomial. Adv Appl Math 32:5\u20139","journal-title":"Special issue on the Tutte polynomial. Adv Appl Math"},{"key":"9_CR108_9","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1006\/jctb.1998.1860","volume":"74","author":"D Vertigan","year":"1998","unstructured":"Vertigan D (1998) Bicycle dimension and special points of the Tutte polynomial. J Combin Theory B 74:378\u2013396","journal-title":"J Combin Theory B"},{"key":"9_CR109_9","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1017\/S0963548300000195","volume":"1","author":"DL Vertigan","year":"1992","unstructured":"Vertigan DL, Welsh DJA (1992) The computational complexity of the Tutte plane: the bipartite case. Combinator Probab Comput 1:181\u2013187","journal-title":"Combinator Probab Comput"},{"key":"9_CR110_9","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511752506","volume-title":"Complexity: knots, colorings and counting","author":"DJA Welsh","year":"1993","unstructured":"Welsh DJA (1993) Complexity: knots, colorings and counting. Cambridge University Press, Cambridge"},{"key":"9_CR111_9","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<210::AID-RSA2>3.0.CO;2-R","volume":"15","author":"DJA Welsh","year":"1999","unstructured":"Welsh DJA (1999) The Tutte polynomial, in statistical physics methods in discrete probability, combinatorics, and theoretical computer science. Random Struct Algorithm 15:210\u2013228","journal-title":"Random Struct Algorithm"},{"key":"9_CR112_9","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1063\/1.533181","volume":"41","author":"DJA Welsh","year":"2000","unstructured":"Welsh DJA, Merino C (2000) The Potts model and the Tutte polynomial. J Math Phys 41:1127\u20131152","journal-title":"J Math Phys"},{"key":"9_CR113_9","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1090\/S0002-9904-1932-05460-X","volume":"38","author":"H Whitney","year":"1932","unstructured":"Whitney H (1932) A logical expansion in mathematics. Bull Am Math Soc 38:572\u2013579","journal-title":"Bull Am Math Soc"},{"key":"9_CR114_9","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0012-365X(92)90614-L","volume":"101","author":"D Woodall","year":"1992","unstructured":"Woodall D (1992) A zero-free interval for chromatic polynomials. Discrete Math 101: 333\u2013341","journal-title":"Discrete Math"},{"key":"9_CR115_9","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/0095-8956(90)90127-L","volume":"48","author":"D Yetter","year":"1990","unstructured":"Yetter D (1990) On graph invariants given by linear recurrence relations. J Combin Theory B 48:6\u201318","journal-title":"J Combin Theory B"},{"key":"9_CR116_9","doi-asserted-by":"crossref","unstructured":"Zaslavsky T (1975) Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Mem Am Math Soc 154. American Mathematical Society, Providence, RI","DOI":"10.1090\/memo\/0154"},{"key":"9_CR117_9","volume-title":"Combinatorial geometries, encyclopedia of mathematics and its applications","author":"T Zaslavsky","year":"1987","unstructured":"Zaslavsky T (1987) The M\u00f6bius function and the characteristic polynomial. In: White N (ed) Combinatorial geometries, encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge"},{"key":"9_CR118_9","volume-title":"Integer flows and cycle covers of graphs","author":"CQ Zhang","year":"1997","unstructured":"Zhang CQ (1997) Integer flows and cycle covers of graphs. Marcel Dekker Inc., New York"}],"container-title":["Structural Analysis of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-8176-4789-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T23:48:09Z","timestamp":1675727289000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-8176-4789-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,16]]},"ISBN":["9780817647889","9780817647896"],"references-count":118,"URL":"https:\/\/doi.org\/10.1007\/978-0-8176-4789-6_9","relation":{},"subject":[],"published":{"date-parts":[[2010,9,16]]},"assertion":[{"value":"16 September 2010","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}