Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T00:57:11.690Z Has data issue: false hasContentIssue false
  • English
  • Français

Location of Zeros of Chromatic and Related Polynomials of Graphs

Published online by Cambridge University Press:  20 November 2018

Francesco Brenti ,
Gordon F. Royle  and
David G. Wagner
Francesco Brenti
Affiliation:
Dipartimento di Matematica Universita' di Perugia Via Vanvitelli 1 1-06123, Perugia Italy
Gordon F. Royle
Affiliation:
Department of Computer Science University of Western Australia Perth, Western Australia Australia
David G. Wagner
Affiliation:
Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario N2L 3G1
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

05C1505A1530C1526C10
Type
Research Article
Information
Canadian Journal of Mathematics , Volume 46 , Issue 1 , 01 February 1994 , pp. 55 - 80
Copyright
Copyright © Canadian Mathematical Society 1994

References

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. 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. Biggs, N. L., Algebraic Graph Theory, Cambridge Tracts in Math. 67, Cambridge U.P., Cambridge, 1974.Google Scholar
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. 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. Birkhoff, G. D. and Lewis, D. C., Chromatic polynomials, Trans. Amer. Math. Soc. 60( 1946), 355–451.Google Scholar
7. Bjorner, A., The unimodality conjecture for convex poly topes, Bull. Amer. Math. Soc. 4(1980), 187–188.Google Scholar
8. Brenti, F., Unimodal, Log-concave, and Pôlya Frequency Sequences in Combinatorics, Mem. Amer. Math. Soc. 413, Providence, RI, (1989).Google Scholar
9. Brenti, F., Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc. 332(1992), 729–756.Google Scholar
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. Compton, K. J., A logical approach to asymptotic combinatorics I. First order properties, Adv. in Math. 65(1987), 65–96.Google Scholar
12. Comtet, L., Advanced Combinatorics, D. Reidel, Dordrecht, 1974.Google Scholar
13. Crapo, H. H., The Tutte polynomial, Aequationes Math. 3(1969), 211–229.Google Scholar
14. Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25(1961), 71–76.Google Scholar
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. Godsil, C. D., Matchings and walks in graphs, J. Graph Theory 5( 1981 ), 285–297.Google Scholar
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. Heilmann, O. J. and Lieb, E. H., Theory of monômer-dimer systems, Comm. Math. Phys. 25(1972), 190–232.Google Scholar
19. Hoggar, S., Chromatic polynomials and logarithmic concavity, J. Comb. Theory Ser. B 16(1974), 248- 254.Google Scholar
20. Karlin, S., Total Positivity, vol., Stanford U.P, Stanford, 1968.Google Scholar
21. Korfhage, R. R., a-polynomials and graph coloring, J. Comb. Theory Ser. B 24( 1978), 137–153.Google Scholar
22. Lovâsz, L., Combinatorial Problems and Exercises, North-Holland, Amsterdam, New York, 1979.Google Scholar
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. Read, R. C., An introduction to chromatic polynomials, J. Comb. Theory 4(1968), 52–71.Google Scholar
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. 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. 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. Stanley, R. P., Acyclic orientations of graphs, Discrete Math. 5( 1973), 171–178.Google Scholar
29. Stanley, R. P., Enumerative Combinatorics, vol. I, Wadsworth & Brooks/Cole, Monterey, CA, 1986.Google Scholar
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. Thier, V., Graphen und Polynôme, Diploma Thesis, T.U. München, München, 1983.Google Scholar
32. Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math. 6(1954), 80–91.Google Scholar
33. Tutte, W. T., On chromatic polynomials and the golden ratio, J. Comb. Theory 9(1970), 289–296.Google Scholar
34. Tutte, W. T., Chromatic sums for planar triangulations, Canad. J. Math. 26(1974), 893–907.Google Scholar
35. Tutte, W. T., Chromials, in Springer Lecture Notes in Math. 411(1974), 243–266.Google Scholar
36. Wagner, D. G., The partition polynomial of a finite set system, J. Comb. Theory Ser. A 56(1991), 138–159.Google Scholar
37. Wagner, D. G.,Total positivity of Hadamardproducts, J. Math. Anal. Appl. 163(1992), 459–483.Google Scholar
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. Whitney, H., A logical expansion in mathematics, Bull. Amer. Math. Soc. 38(1932), 572–579.Google Scholar
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. 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