{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T02:57:40Z","timestamp":1782183460468,"version":"3.54.5"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1996,9,1]],"date-time":"1996-09-01T00:00:00Z","timestamp":841536000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1996,9]]},"DOI":"10.1007\/bf01261322","type":"journal-article","created":{"date-parts":[[2005,3,23]],"date-time":"2005-03-23T22:01:48Z","timestamp":1111615308000},"page":"383-397","source":"Crossref","is-referenced-by-count":11,"title":["Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph"],"prefix":"10.1007","volume":"16","author":[{"given":"Nabil","family":"Kahale","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonard J.","family":"Schulman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"no. 2","key":"CR1","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1002\/rsa.3240010204","volume":"1","author":"N. Alon","year":"1990","unstructured":"N. Alon: The number of spanning trees in regular graphs,Random Structures & Algorithms 1 (1990), no. 2, 175?181.","journal-title":"Random Structures & Algorithms"},{"key":"CR2","unstructured":"N. Alon, andJ. H. Spencer:The Probabilistic Method, Wiley, 1992."},{"key":"CR3","unstructured":"N. Alon, andN. Kahale: personal communication, August 1993."},{"issue":"no. 3","key":"CR4","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1017\/S0963548300001188","volume":"3","author":"J. D. Annan","year":"1994","unstructured":"J. D. Annan:A randomized approximation algorithm for counting the number of forests in dense graphs, Combinatorics, Probability and Computing3 (1994), no. 3, 273?283.","journal-title":"Probability and Computing"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"N. Biggs:Algebraic Graph Theory, Cambridge University Press, 1974.","DOI":"10.1017\/CBO9780511608704"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"J. A. Bondy, andU. S. R. Murty:Graph Theory and Applications, American Elsevier, 1976.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff: A measure for asymptotic efficiency of tests of a hypothesis based on the sum of observations,Ann. Math. Statist.,23 (1952), 493?507.","journal-title":"Ann. Math. Statist."},{"issue":"no. 3","key":"CR8","first-page":"251","volume":"12","author":"P. Erd?s","year":"1963","unstructured":"P. Erd?s, andH. Sachs: Regulare Graphe gegebener Taillenweite mit minimaler Knotenzahl,Wiss. Z. Univ. Halle-Wittenberg, Math.-Nat.,12 (1963), no. 3, 251?258.","journal-title":"Wiss. Z. Univ. Halle-Wittenberg, Math.-Nat."},{"issue":"no. 2","key":"CR9","first-page":"272","volume":"22","author":"W. Goddard","year":"1993","unstructured":"W. Goddard, C. Kenyon, V. King, andL. J. Schulman:Optimal Randomized Algorithms for Local Sorting and Set-Maxima, SIAM J. Computing,22 (1993), no. 2, 272?283; Also in: Optimal Randomized Algorithms for Local Sorting and Set-Maxima, W. Goddard, V. King and L. Schulman, Proc. Twenty Second Annual ACM Symp. on Theory of Computing (1990), 45?53.","journal-title":"Optimal Randomized Algorithms for Local Sorting and Set-Maxima, SIAM J. Computing"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"F. Jaeger","year":"1990","unstructured":"F. Jaeger, D. L. Vertigan, andD. J. A. Welsh: On the Computational Complexity of the Jones and Tutte Polynomials,Proceedings of the Cambridge Philosophical Society, vol.108 (1990), 35?53.","journal-title":"Proceedings of the Cambridge Philosophical Society"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1145\/322203.322206","volume":"27","author":"R. Graham","year":"1980","unstructured":"R. Graham, F. Yao, andA. Yao: Information Bounds are Weak in the Shortest Distance Problem,J. ACM,27 (1980), 428?444.","journal-title":"J. ACM"},{"key":"CR12","unstructured":"N. Kahale:Expander Graphs. PhD thesis, Massachusetts Institute of Technology, September 1993. MIT Laboratory for Computer Science, Technical Report MIT\/LCS\/TR-591."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/0607036","volume":"7","author":"N. Linial","year":"1986","unstructured":"N. Linial: Hard enumeration problems in geometry and combinatorics,SIAM J. on Algebraic and Discrete Methods,7 (1986), 331?335.","journal-title":"SIAM J. on Algebraic and Discrete Methods"},{"issue":"no. 3","key":"CR14","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzky","year":"1988","unstructured":"A. Lubotzky, R. Phillips, andP. Sarnak: Ramanujan graphs,Combinatorica,8 (1988), no. 3, 261?277.","journal-title":"Combinatorica"},{"key":"CR15","unstructured":"M. Marcus, andH. Minc: A Survey of Matrix Theory and Matrix Inequalities, Prindle Weber and Schmidt 1964, Dover 1992, \ufffdII.4.1.7 114."},{"issue":"no. 1","key":"CR16","first-page":"51","volume":"24","author":"G. A. Margulis","year":"1988","unstructured":"G. A. Margulis: Explicit group-theoretical constructions of combinatorial schemes and their applications to the design of expanders and concentrators,Problemy Pereda?i Informacii,24 (1988), no. 1, 51?60.","journal-title":"Problemy Pereda?i Informacii"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0195-6698(83)80045-6","volume":"4","author":"B. D. McKay","year":"1983","unstructured":"B. D. McKay: Spanning trees in regular graphs,Euro. J. Combinatorics,4 (1983), 149?160.","journal-title":"Euro. J. Combinatorics"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1137\/0213008","volume":"13","author":"U. Manber","year":"1984","unstructured":"U. Manber, andM. Tompa: The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem,SIAM J. Comp.,13 (1984), 109?115.","journal-title":"SIAM J. Comp."},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"R. P. Stanley:Enumerative Combinatorics, Wadsworth & Brooks\/Cole, 1986.","DOI":"10.1007\/978-1-4615-9763-6"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0012-365X(73)90108-8","volume":"5","author":"R. P. Stanley","year":"1973","unstructured":"R. P. Stanley: Acyclic Orientations of Graphs,Discrete Mathematics,5 (1973), 171?178.","journal-title":"Discrete Mathematics"},{"issue":"No. 4","key":"CR21","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1137\/0403050","volume":"3","author":"L. Tak\ufffdcs","year":"1990","unstructured":"L. Tak\ufffdcs: On the Number of Distinct Forests,SIAM J. Discrete Math, Vol.3, No. 4, Nov. 1990, 574?581.","journal-title":"SIAM J. Discrete Math"},{"key":"CR22","unstructured":"J. S. Vitter, andP. Flajolet: Average-case analysis of algorithms and data structures, Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, MIT press (edited by J. Van Leeuwen), 1990, 433?524."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01261322.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01261322\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01261322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T12:37:52Z","timestamp":1586176672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01261322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["BF01261322"],"URL":"https:\/\/doi.org\/10.1007\/bf01261322","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}