## Annals of Combinatorics 3 (1999) 417-429Forests, Colorings and Acyclic Orientations of the Square Lattice C. Merino and D.J.A. Welsh Mathematical Institute, 24--26 St. Giles, Oxford University, OX1 3LB, UK
Received December 11, 1998
References
1. N. Alon, A.M. Frieze, and D.J.A. Welsh, Polynomial time randomised approximation schemes for Tutte-Grothendieck invariants: The dense case, Random Struct. Algorithms 6 (1995) 459–478. 2. A. Andrzejak, An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math. 190 (1998) 39–54. 3. J.D. Annan, A randomised approximation algorithm for counting the number of forests in dense graphs, Combin. Prob. Comput. 3 (1994) 273–283. 4. A.V. Bakaev and V.I. Kabanovich, Series expansions for the $q$-colour problem on the square and cubic lattices, J. Phys. A 27 (1994) 6731–6739. 5. F. Berman et al., Generalized planar matching, J. Algorithms 11 (1990) 153–184. 6. N.L. Biggs, Chromatic and thermodynamic limits, J. Phys. A 8 (1975) L 110–112. 7. N.L. Biggs, Colouring square lattice graphs, Bull. London Math. Soc. 9 (1977) 54–56. 8. N.L. Biggs and G.H.J. Meredith, Approximations for chromatic polynomials, J. Combin. Theory Ser. B 20 (1976) 5–19. 9. T.H. Brylawski and J.G. Oxley, The Tutte polynomial and its applications, In: Matroid Applications, N. White, Ed., Cambridge University Press, 1992, pp. 123–225. 10. C.M. Fortuin and P.W. Kasteleyn, On the random cluster model. I. Introduction and relation to other models, Physica 57 (1972) 536–564. 11. M.R. Garey and D.S. Johnson, The rectilinear Steiner problem is NP-complete, SIAM J. Appl. Math.~{\bf 32} (1977) 826–834. 12. M.R. Garey and D.S. Johnson, Computers and Intractability --- A Guide to the Theory of NP-completeness, W.H. Freeman, San Francisco, 1979. 13. G.R. Grimmett, Multidimensional lattices and their partition function, Quart. J. Math. Oxford 29 (1978) 141–157. 14. G.R. Grimmett, The rank polynomials of large random lattices, J. London Math. Soc. 18 (1978) 567–575. 15. A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter, Hamilton paths in grid graphs, SIAM J. Comput. 11 (1982) 676–686. 16. F. Jaeger, D.L. Vertigan, and D.J.A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Camb. Phil. Soc. 108 (1990) 35–53. 17. M. Jerrum, A very simple algorithm for estimating the number of $k$-colourings of a low-degree graph, Random Struct. Algorithms 7 (1995) 157–165. 18. M. Jerrum, Mathematical foundations of Markov chain Monte Carlo method, In: Probabilistic Methods for Algorithmic Discrete Mathematics, M. Habib et al., Eds., Algorithms and Combinatorics, Vol. 16, Springer-Verlag, 1998, pp. 116–165. 19. D.S. Johnson, The NP-completeness column: An ongoing guide, J. Algorithms 6 (1985) 434–451. 20. N.E.~Kahale and L.J.~Schulman, Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph, Combinatorica 16 (1996) 383–397. 21. D. Kim and I.G. Enting, The limit of chromatic polynomials, J. Combin. Theory Ser. B 26 (1979) 327–336. 22. E. Lieb, The residual entropy of square ice, Phys. Rev. 162 (1967) 162–172. 23. L. Lovász, Combinatorial Problems and Exercises, North-Holland Pub. Co., Amsterdam, 1979, pp. 238–243. 24. D.B. Massey et al., Lènumbers of arrangements and matroid identities, J. Combin. Theory Ser. B 70 (1997) 118–133. 25. C.J.H. McDiarmid, Private communication. 26. J.F. Nagle, A new subgraph expansion for obtaining coloring polynomials for graphs, J. Combin. Theory Ser. B 10 (1971) 42–59. 27. S. Noble, Evaluating the Tutte polynomial for graphs of bounded tree-width, Combin. Prob. Comput. 7 (3) (1998) 307–322. 28. J.G. Propp and D.B. Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Struct. Algorithms 9 (1996) 223–252. 29. N. Robertson and P.D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms 7 (1986) 309–322. 30. J. Salas and A.D. Sokal, Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem, J. Stat. Phys. 86 (1997) 551–579. 31. R.P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973) 171–178. 32. H.N.V. Temperley, Combinatorics, London Mathematical Society Lecture Notes Series, Vol. 13, Cambridge University Press, 1974, pp. 202–204. 33. C.J.~Thompson, Mathematical Statistical Mechanics, Princeton University Press, Princeton, 1979, pp. 131–135. 34. D.L. Vertigan and D.J.A.~Welsh, The computational complexity of the Tutte plane: The bipartite case, Combin. Prob. Comput. 1 (1992) 181–187. 35. D.J.A. Welsh, Complexity: Knots, Colourings and Counting, London Mathematical Society Lecture Notes Series, Vol. 186, Cambridge University Press, 1993. |