Location of Zeros of Chromatic and Related Polynomials of Graphs

Brenti, Francesco ; Royle, Gordon F. ; Wagner, David G.

Canadian journal of mathematics, Tome 46 (1994) no. 1, pp. 55-80

Résumé

We consider the location of zeros of four related classes of polynomials, one of which is the class of chromatic polynomials of graphs. All of these polynomials are generating functions of combinatorial interest. Extensive calculations indicate that these polynomials often have only real zeros, and we give a variety of theoretical results which begin to explain this phenomenon. In the course of the investigation we prove a number of interesting combinatorial identities and also give some new sufficient conditions for a polynomial to have only real zeros.

Détail

DOI : 10.4153/CJM-1994-002-3

Mots-clés : 05C15, 05A15, 30C15, 26C10

Bibliographie

[1] 1. Beraha, S., Kahane, J. and Weiss, N. J., Limits of zeros of recursively defined families of polynomials. In: Studies in Foundations and Combinatorics, (ed. G.-C. Rota), Adv. in Math., Supplementary Studies 1, Academic Press, New York, 1978, 213–232. Google Scholar

[2] 2. Beraha, S., Kahane, J. and Weiss, N. J., Limits of chromatic zeros of some families of graphs, J. Combin. Theory Ser. B 28(1980), 52–65. Google Scholar

[3] 3. Biggs, N. L., Algebraic Graph Theory, Cambridge Tracts in Math. 67, Cambridge U.P., Cambridge, 1974. Google Scholar

[4] 4. Biggs, N. L., Damerell, R. M. and Sands, D. A., Recursive families of graphs, J. Combin. Theory Ser. B 12(1972), 123–131. Google Scholar

[5] 5. Birkhoff, G. D., A determinantal formula for the number of ways of coloring a map, Ann. of Math. 14(1912), 42–46. Google Scholar

[6] 6. Birkhoff, G. D. and Lewis, D. C., Chromatic polynomials, Trans. Amer. Math. Soc. 60( 1946), 355–451. Google Scholar

[7] 7. Bjorner, A., The unimodality conjecture for convex poly topes, Bull. Amer. Math. Soc. 4(1980), 187–188. Google Scholar

[8] 8. Brenti, F., Unimodal, Log-concave, and Pôlya Frequency Sequences in Combinatorics, Mem. Amer. Math. Soc. 413, Providence, RI, (1989). Google Scholar

[9] 9. Brenti, F., Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc. 332(1992), 729–756. Google Scholar

[10] 10. Cameron, R. D., Colbourn, C. J., Read, R. C. and Wormald, N. C., Cataloguing the graphs on 10 vertices, J. Graph Theory 9(1985), 551–562. Google Scholar

[11] 11. Compton, K. J., A logical approach to asymptotic combinatorics I. First order properties, Adv. in Math. 65(1987), 65–96. Google Scholar

[12] 12. Comtet, L., Advanced Combinatorics, D. Reidel, Dordrecht, 1974. Google Scholar

[13] 13. Crapo, H. H., The Tutte polynomial, Aequationes Math. 3(1969), 211–229. Google Scholar

[14] 14. Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25(1961), 71–76. Google Scholar

[15] 15. Gernert, D., A survey of partial proofs for Read's conjecture and some recent results. In: IX Symposium on operations research, part I, sections 1-4, Osnabruck, (1984), Methods Oper. Res. 49, Athenaum/Hain/Hanstein, Konigstein/Ts., 1985, 233–238. Google Scholar

[16] 16. Godsil, C. D., Matchings and walks in graphs, J. Graph Theory 5( 1981 ), 285–297. Google Scholar

[17] 17. Goldman, J. R., Joichi, J. T. and White, D. E., Rook Theory III: Rook polynomials and the chromatic structure of graphs, J. Comb. Theory Ser. B 25(1978), 135–142. Google Scholar

[18] 18. Heilmann, O. J. and Lieb, E. H., Theory of monômer-dimer systems, Comm. Math. Phys. 25(1972), 190–232. Google Scholar

[19] 19. Hoggar, S., Chromatic polynomials and logarithmic concavity, J. Comb. Theory Ser. B 16(1974), 248- 254. Google Scholar

[20] 20. Karlin, S., Total Positivity, vol., Stanford U.P, Stanford, 1968. Google Scholar

[21] 21. Korfhage, R. R., a-polynomials and graph coloring, J. Comb. Theory Ser. B 24( 1978), 137–153. Google Scholar

[22] 22. Lovâsz, L., Combinatorial Problems and Exercises, North-Holland, Amsterdam, New York, 1979. Google Scholar

[23] 23. McKay, B. D. and Royle, G. F., Constructing the cubic graphs on up to 20 vertices, Ars Combin. 21-A(1986), 129–140. Google Scholar

[24] 24. Read, R. C., An introduction to chromatic polynomials, J. Comb. Theory 4(1968), 52–71. Google Scholar

[25] 25. Read, R. C., An improved method for computing chromatic polynomials of sparse graphs, Proceedings of the Sixth Carribean Conference on Combinatorics and Computing, Trinidad, 1991, to appear. Google Scholar

[26] 26. Read, R. C. and Royle, G. F., Chromatic roots of families of graphs, in Graph Theory, Combinatorics, and Applications, (eds. Alavi, Chartrand, Oellermann, Schwenk), J. Wiley, New York, 1991. Google Scholar

[27] 27. Read, R. C. and Tutte, W. T., Chromatic polynomials.In: Selected Topics in Graph Theory 3 (eds. Beineke, Wilson), Academic Press, New York, 1988. Google Scholar

[28] 28. Stanley, R. P., Acyclic orientations of graphs, Discrete Math. 5( 1973), 171–178. Google Scholar

[29] 29. Stanley, R. P., Enumerative Combinatorics, vol. I, Wadsworth & Brooks/Cole, Monterey, CA, 1986. Google Scholar

[30] 30. Stanley, R. P., Log-concave and unimodal sequences in algebra, combinatorics, and geometry. In: Graph Theory and Applications: East and West (eds. Capobianco, Guan, Hsu, Tian), Annals of the New York Acad. Sci. 576(1989), 500–535. Google Scholar

[31] 31. Thier, V., Graphen und Polynôme, Diploma Thesis, T.U. München, München, 1983. Google Scholar

[32] 32. Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math. 6(1954), 80–91. Google Scholar

[33] 33. Tutte, W. T., On chromatic polynomials and the golden ratio, J. Comb. Theory 9(1970), 289–296. Google Scholar

[34] 34. Tutte, W. T., Chromatic sums for planar triangulations, Canad. J. Math. 26(1974), 893–907. Google Scholar

[35] 35. Tutte, W. T., Chromials, in Springer Lecture Notes in Math. 411(1974), 243–266. Google Scholar

[36] 36. Wagner, D. G., The partition polynomial of a finite set system, J. Comb. Theory Ser. A 56(1991), 138–159. Google Scholar

[37] 37. Wagner, D. G.,Total positivity of Hadamardproducts, J. Math. Anal. Appl. 163(1992), 459–483. Google Scholar

[38] 38. Wagner, D. G., Zeros of rank-generating functions of Cohen-Macaulay complexes. In: Proceedings of the 4th Conference on Formal Power Series and Algebraic Combinatorics, (eds. Labelle and Reutenauer), UQAM, Montreal, 1992. Google Scholar

[39] 39. Whitney, H., A logical expansion in mathematics, Bull. Amer. Math. Soc. 38(1932), 572–579. Google Scholar

[40] 40. Wilf, H. S., Which polynomials are chromatic?, Colloq. Internaz. sulle Teorie Combinatorie, 1973 (ed. B. Segre), Atti dei Convegni Lincei 17, Rome, 1976, 247–256. Google Scholar

[41] 41. Woodall, D. R., Zeros of chromatic polynomials, Combinatorial Surveys: Proc. Sixth British Combinatorial Conf. (ed. Cameron, P. J.), Academic Press, London, 1977, 199–223. Google Scholar