{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:29:20Z","timestamp":1780381760057,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":56,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662529201","type":"print"},{"value":"9783662529218","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-52921-8_18","type":"book-chapter","created":{"date-parts":[[2016,8,5]],"date-time":"2016-08-05T15:22:30Z","timestamp":1470410550000},"page":"279-296","source":"Crossref","is-referenced-by-count":1,"title":["Semantic Equivalence of Graph Polynomials Definable in Second Order Logic"],"prefix":"10.1007","author":[{"given":"Johann A.","family":"Makowsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elena V.","family":"Ravve","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,8,6]]},"reference":[{"issue":"1","key":"18_CR1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"N Alon","year":"1985","unstructured":"Alon, N., Milman, V.: $$\\lambda $$ 1, isoperimetric inequalities for graphs, and superconcentrators. J. Comb. Theory Ser. B 38(1), 73\u201388 (1985)","journal-title":"J. Comb. Theory Ser. B"},{"key":"18_CR2","unstructured":"Anari, N., Gharan, S.O., Rezaei, A.: Monte carlo markov chains for sampling strongly rayleigh distributions and determinantal point processes (2016). arXiv preprint arXiv:1602.05242"},{"issue":"1","key":"18_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejc.2009.05.006","volume":"31","author":"I Averbouch","year":"2010","unstructured":"Averbouch, I., Godlin, B., Makowsky, J.A.: An extension of the bivariate chromatic polynomial. Eur. J. Comb. 31(1), 1\u201317 (2010)","journal-title":"Eur. J. Comb."},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0167-5060(08)70380-7","volume":"35","author":"AT Balaban","year":"1993","unstructured":"Balaban, A.T.: Solved and unsolved problems in chemical graph theory. quo vadis, graph theory? Ann. Discrete Math. 35, 109\u2013126 (1993)","journal-title":"Ann. Discrete Math."},{"key":"18_CR5","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1021\/ci00025a001","volume":"35","author":"AT Balaban","year":"1995","unstructured":"Balaban, A.T.: Chemical graphs: looking back and glimpsing ahead. J. Chem. Inf. Comput. Sci. 35, 339\u2013350 (1995)","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"18_CR6","doi-asserted-by":"crossref","first-page":"42","DOI":"10.2307\/1967597","volume":"14","author":"GD 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":"18_CR7","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.: Modern Graph Theory. Springer, New York (1998)"},{"issue":"2","key":"18_CR8","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1215\/00127094-2008-018","volume":"143","author":"J Borcea","year":"2008","unstructured":"Borcea, J., Br\u00e4nd\u00e9n, P., et al.: Applications of stable polynomials to mixed determinants: johnson\u2019s conjectures, unimodality, and symmetrized fischer products. Duke Math. J. 143(2), 205\u2013223 (2008)","journal-title":"Duke Math. J."},{"issue":"2","key":"18_CR9","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1090\/S0894-0347-08-00618-8","volume":"22","author":"J Borcea","year":"2009","unstructured":"Borcea, J., Br\u00e4nd\u00e9n, P., Liggett, T.: Negative dependence and the geometry of polynomials. J. Am. Math. Soc. 22(2), 521\u2013567 (2009)","journal-title":"J. Am. Math. Soc."},{"issue":"1","key":"18_CR10","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/j.aim.2007.05.011","volume":"216","author":"P Br\u00e4nd\u00e9n","year":"2007","unstructured":"Br\u00e4nd\u00e9n, P.: Polynomials with the half-plane property and matroid theory. Adv. Math. 216(1), 302\u2013320 (2007)","journal-title":"Adv. Math."},{"key":"18_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-1939-6","volume-title":"Spectra of Graphs. Universitext","author":"AE Brouwer","year":"2012","unstructured":"Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Universitext. Springer, New York (2012)"},{"issue":"3","key":"18_CR12","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1023\/B:JACO.0000030703.39946.70","volume":"19","author":"JI Brown","year":"2004","unstructured":"Brown, J.I., Hickman, C.A., Nowakowski, R.J.: On the location of roots of independence polynomials. J. Algebraic Comb. 19(3), 273\u2013282 (2004)","journal-title":"J. Algebraic Comb."},{"issue":"1","key":"18_CR13","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0196-8858(03)00078-2","volume":"32","author":"YB Choe","year":"2004","unstructured":"Choe, Y.B., Oxley, J.G., Sokal, A.D., Wagner, D.G.: Homogeneous multivariate polynomials with the half-plane property. Adv. Appl. Math. 32(1), 88\u2013187 (2004)","journal-title":"Adv. Appl. Math."},{"issue":"1\u20132","key":"18_CR14","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. Discrete Appl. Math. 108(1\u20132), 23\u201352 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"8","key":"18_CR15","doi-asserted-by":"crossref","first-page":"1407","DOI":"10.1016\/j.ejc.2011.06.009","volume":"32","author":"P Csikv\u00e1ri","year":"2011","unstructured":"Csikv\u00e1ri, P., Oboudi, M.R.: On the roots of edge cover polynomials of graphs. Eur. J. Comb. 32(8), 1407\u20131416 (2011)","journal-title":"Eur. J. Comb."},{"key":"18_CR16","volume-title":"Spectra of Graphs","author":"DM Cvetkovi\u0107","year":"1995","unstructured":"Cvetkovi\u0107, D.M., Doob, M., Sachs, H.: Spectra of Graphs, 3rd edn. Johann Ambrosius Barth, Heidelberg (1995)","edition":"3"},{"key":"18_CR17","doi-asserted-by":"crossref","DOI":"10.1142\/5814","volume-title":"Chromaticity of Graphs","author":"FM Dong","year":"2005","unstructured":"Dong, F.M., Koh, K.M., Teo, K.L., Polynomials, C.: Chromaticity of Graphs. World Scientific, Singapore (2005)"},{"key":"18_CR18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-0-8176-4789-6_9","volume-title":"Structural Analysis of Complex Networks","author":"JA Ellis-Monaghan","year":"2011","unstructured":"Ellis-Monaghan, J.A., Merino, C.: Graph polynomials and their applications i: the tutte polynomial. In: Dehmer, M. (ed.) Structural Analysis of Complex Networks, pp. 219\u2013255. Springer, Heidelberg (2011)"},{"key":"18_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/558\/11047","volume-title":"Model Theoretic Methods in Finite Combinatorics (Contemporary Mathematics)","author":"E Fischer","year":"2011","unstructured":"Fischer, E., Kotek, T., Makowsky, J.A.: Application of logic to combinatorial sequences and their recurrence relations. In: Grohe, M., Makowsky, J.A. (eds.) Model Theoretic Methods in Finite Combinatorics (Contemporary Mathematics), vol. 558, pp. 1\u201342. American Mathematical Society, Providence (2011)"},{"issue":"2","key":"18_CR20","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1093\/logcom\/exq006","volume":"22","author":"B Godlin","year":"2012","unstructured":"Godlin, B., Katz, E., Makowsky, J.A.: Graph polynomials: from recursive definitions to subset expansion formulas. J. Log. Comput. 22(2), 237\u2013265 (2012)","journal-title":"J. Log. Comput."},{"key":"18_CR21","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1002\/jgt.3190050203","volume":"5","author":"CD Godsil","year":"1981","unstructured":"Godsil, C.D., Gutman, I.: On the theory of the matching polynomial. J. Graph Theory 5, 137\u2013144 (1981)","journal-title":"J. Graph Theory"},{"issue":"3","key":"18_CR22","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0020-0190(00)00086-7","volume":"75","author":"M Goldwurm","year":"2000","unstructured":"Goldwurm, M., Santini, M.: Clique polynomials have a unique root of smallest modulus. Inf. Process. Lett. 75(3), 127\u2013132 (2000)","journal-title":"Inf. Process. Lett."},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Gurvits, L.: Hyperbolic polynomials approach to van der waerden\/schrijver-valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 417\u2013426. ACM (2006)","DOI":"10.1145\/1132516.1132578"},{"issue":"5","key":"18_CR24","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1002\/cpa.20155","volume":"60","author":"JW Helton","year":"2007","unstructured":"Helton, J.W., Vinnikov, V.: Linear matrix inequality representation of sets. Commun. Pure Appl. Math. 60(5), 654\u2013674 (2007)","journal-title":"Commun. Pure Appl. Math."},{"key":"18_CR25","unstructured":"Hirasawa, M., Murasugi, K.: Various stabilities of the alexander polynomials of knots and links (2013). arXiv preprint arXiv:1307.1578"},{"key":"18_CR26","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. Discrete Math. 125, 219\u2013228 (1994)","journal-title":"Discrete Math."},{"key":"18_CR27","unstructured":"Hoshino, R.: Independence polynomials of circulant graphs. Ph.D. thesis, Dalhousie University, Halifax, Nova Scotia (2007)"},{"issue":"2","key":"18_CR28","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF01446812","volume":"46","author":"A Hurwitz","year":"1895","unstructured":"Hurwitz, A.: Ueber die bedingungen, unter welchen eine gleichung nur wurzeln mit negativen reellen theilen besitzt. Math. Ann. 46(2), 273\u2013284 (1895)","journal-title":"Math. Ann."},{"key":"18_CR29","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":"18_CR30","unstructured":"Kotek, T.: Definability of combinatorial functions: Ph.D. thesis, Technion - Israel Institute of Technology, Haifa, Israel, March 2012"},{"key":"18_CR31","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1090\/conm\/558\/11052","volume-title":"Model Theoretic Methods in Finite Combinatorics (Contemporary Mathematics)","author":"T Kotek","year":"2011","unstructured":"Kotek, T., Makowsky, J.A., Zilber, B.: On counting generalized colorings. In: Grohe, M., Makowsky, J.A. (eds.) Model Theoretic Methods in Finite Combinatorics (Contemporary Mathematics), vol. 558, pp. 207\u2013242. American Mathematical Society, Providence (2011)"},{"key":"18_CR32","volume-title":"Matching Theory, Annals of Discrete Mathematics","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D., Theory, M.: Matching Theory, Annals of Discrete Mathematics, vol. 29. North Holland Publishing, North Holland (1986)"},{"issue":"3","key":"18_CR33","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1016\/j.jctb.2006.06.001","volume":"97","author":"P Seymour","year":"2007","unstructured":"Seymour, P., Chudnovsky, M.: The roots of the independence polynomial of a clawfree graph. J. Comb. Theory Ser. B 97(3), 350\u2013357 (2007)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1\u20133","key":"18_CR34","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"JA Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Ann. Pure Appl. Log. 126(1\u20133), 159\u2013213 (2004)","journal-title":"Ann. Pure Appl. Log."},{"key":"18_CR35","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1007\/s00224-007-9022-9","volume":"43","author":"JA Makowsky","year":"2008","unstructured":"Makowsky, J.A.: From a zoo to a zoology: towards a general theory of graph polynomials. Theory Comput. Syst. 43, 542\u2013562 (2008)","journal-title":"Theory Comput. Syst."},{"key":"18_CR36","doi-asserted-by":"crossref","unstructured":"Makowsky, J.A., Kotek, T., Ravve, E.V.: A computational framework for the study of partition functions and graph polynomials. In: Proceedings of the 12th Asian Logic Conference 2011, pp. 210\u2013230. World Scientific (2013)","DOI":"10.1142\/9789814449274_0012"},{"key":"18_CR37","unstructured":"Makowsky, J.A., Ravve, E.V.: Logical methods in combinatorics, Lecture 11. Course given in 2009 under the number 236605, Advanced Topics, Lecture Notes. http:\/\/www.cs.technion.ac.il\/janos\/"},{"key":"18_CR38","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/j.endm.2013.07.033","volume":"43","author":"JA Makowsky","year":"2013","unstructured":"Makowsky, J.A., Ravve, E.V.: On the location of roots of graph polynomials. Electron. Notes Discrete Math. 43, 201\u2013206 (2013)","journal-title":"Electron. Notes Discrete Math."},{"key":"18_CR39","unstructured":"Makowsky, J.A., Ravve, E.V.: On sequences of polynomials arising from graph invariants, preprint (2016)"},{"key":"18_CR40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejc.2014.03.003","volume":"41","author":"JA Makowsky","year":"2014","unstructured":"Makowsky, J.A., Ravve, E.V., Blanchard, N.K.: On the location of roots of graph polynomials. Eur. J. Comb. 41, 1\u201319 (2014)","journal-title":"Eur. J. Comb."},{"issue":"4","key":"18_CR41","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1017\/S0963548309009845","volume":"18","author":"C Merino","year":"2009","unstructured":"Merino, C., Noble, S.D.: The equivalence of two graph polynomials and a symmetric function. Comb. Probab. Comput. 18(4), 601\u2013615 (2009)","journal-title":"Comb. Probab. Comput."},{"key":"18_CR42","volume-title":"Graphs, Morphisms and Statistical Physics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science","year":"2004","unstructured":"Ne\u0161et\u0159il, J., Winkler, P. (eds.): Graphs, Morphisms and Statistical Physics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 63. AMS, New York (2004)"},{"key":"18_CR43","doi-asserted-by":"crossref","first-page":"1057","DOI":"10.5802\/aif.1706","volume":"49","author":"SD Noble","year":"1999","unstructured":"Noble, S.D., Welsh, D.J.A.: A weighted graph polynomial from chromatic invariants of knots. Ann. Inst. Fourier Grenoble 49, 1057\u20131087 (1999)","journal-title":"Ann. Inst. Fourier Grenoble"},{"key":"18_CR44","unstructured":"Pemantle, R.: Hyperbolicity and stable polynomials in combinatorics and probability (2012). arXiv preprint arXiv:1210.3231"},{"key":"18_CR45","doi-asserted-by":"crossref","unstructured":"Sinclair, A., Srivastava, P.: Lee-Yang theorems and the complexity of computing averages. In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 625\u2013634. ACM (2013)","DOI":"10.1145\/2488608.2488686"},{"issue":"1","key":"18_CR46","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1017\/S0963548300004612","volume":"10","author":"AD Sokal","year":"2001","unstructured":"Sokal, A.D.: Bounds on the complex zeros of (di)chromatic polynomials and potts-model partition functions. Comb. Prob. Comput. 10(1), 41\u201377 (2001)","journal-title":"Comb. Prob. Comput."},{"issue":"2","key":"18_CR47","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1017\/S0963548303006023","volume":"13","author":"AD Sokal","year":"2004","unstructured":"Sokal, A.D.: Chromatic roots are dense in the whole complex plane. Comb. Prob. Comput. 13(2), 221\u2013261 (2004)","journal-title":"Comb. Prob. Comput."},{"key":"18_CR48","doi-asserted-by":"crossref","unstructured":"Sokal, A.D.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In: Survey in Combinatorics, 2005. London Mathematical Society Lecture Notes, vol. 327, pp. 173\u2013226 (2005)","DOI":"10.1017\/CBO9780511734885.009"},{"key":"18_CR49","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":"18_CR50","doi-asserted-by":"crossref","first-page":"80","DOI":"10.4153\/CJM-1954-010-9","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte, W.T.: A contribution to the theory of chromatic polynomials. Can. J. Math. 6, 80\u201391 (1954)","journal-title":"Can. J. Math."},{"key":"18_CR51","doi-asserted-by":"crossref","unstructured":"Vishnoi, N.K.: A permanent approach to the traveling salesman problem. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 76\u201380. IEEE (2012)","DOI":"10.1109\/FOCS.2012.81"},{"key":"18_CR52","unstructured":"Vishnoi, N.K.: Zeros of polynomials and their applications to theory: a primer, Preprint. Microsoft Research, Bangalore (2013)"},{"issue":"1","key":"18_CR53","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1090\/S0273-0979-2010-01321-5","volume":"48","author":"DG Wagner","year":"2011","unstructured":"Wagner, D.G.: Multivariate stable polynomials: theory and applications. Bull. Am. Math. Soc. 48(1), 53\u201384 (2011)","journal-title":"Bull. Am. Math. Soc."},{"issue":"6","key":"18_CR54","doi-asserted-by":"crossref","first-page":"1385","DOI":"10.1016\/j.disc.2008.02.005","volume":"309","author":"DG Wagner","year":"2009","unstructured":"Wagner, D.G., Wei, Y.: A criterion for the half-plane property. Discrete Math. 309(6), 1385\u20131390 (2009)","journal-title":"Discrete Math."},{"issue":"6","key":"18_CR55","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1109\/9.293189","volume":"39","author":"K Wang","year":"1994","unstructured":"Wang, K., Michel, A.N., Liu, D.: Necessary and sufficient conditions for the hurwitz and schur stability of interval matrices. IEEE Trans. Autom. Control 39(6), 1251\u20131255 (1994)","journal-title":"IEEE Trans. Autom. Control"},{"key":"18_CR56","unstructured":"Wilf, H.S.: Which polynomials are chromatic. In: Proceedings of Colloquium Combinatorial Theory, Rome (1973)"}],"container-title":["Lecture Notes in Computer Science","Logic, Language, Information, and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-52921-8_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T15:27:26Z","timestamp":1749050846000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-52921-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662529201","9783662529218"],"references-count":56,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-52921-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}