Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-04T21:55:35.395Z Has data issue: false hasContentIssue false

3 - Chromatic polynomials

Published online by Cambridge University Press:  05 May 2015

By
Bill Jackson
Edited by
Lowell W. Beineke  and
Robin J. Wilson
Bill Jackson
Affiliation:
University of Waterloo
Lowell W. Beineke
Affiliation:
Purdue University, Indiana
Robin J. Wilson
Affiliation:
The Open University, Milton Keynes
Get access

Summary

This chapter is concerned with chromatic polynomials and other related polynomials: flow polynomials, characteristic polynomials, Tutte polynomials and the Potts model partition function. We describe their basic properties and state some recent results and open problems. We also outline some techniques for working with these polynomials.

Introduction

The study of chromatic polynomials of graphs was initiated by Birkhoff [3] in 1912 and continued by Whitney [49], [50] in 1932. Inspired by the four-colour conjecture, Birkhoff and Lewis [4] obtained results concerning the distribution of the real zeros of chromatic polynomials of planar graphs and made the stronger conjecture that they have no real zeros greater than or equal to 4. Their hope was that results from analysis and algebra could be used to prove their stronger conjecture, and hence to deduce that the four-colour conjecture was true. This has not yet occurred: indeed, the four-colour conjecture is now a theorem, but the stronger conjecture of Birkhoff and Lewis remains open. Nevertheless, many beautiful results on chromatic polynomials have been obtained, and many other intriguing questions remain unanswered.

Work on chromatic polynomials has received fresh impetus in recent years from an interaction with mathematical physics. The chromatic polynomial is a specialization of the Potts model partition function, used by mathematical physicists to study phase transitions. A combination of ideas and techniques from graph theory and statistical mechanics has led to significant new results on both polynomials. Other recent progress has been made through the use of techniques from algebraic geometry to solve a long-standing open problem concerning the coefficients of chromatic polynomials.

Definitions and elementary properties

All graphs considered are finite and (unless stated otherwise) without loops or multiple edges. As usual, we use G − e to denote the graph obtained by deleting an edge e from a graph G and G/e the graph obtained by contracting e.

Type
Chapter
Information
Topics in Chromatic Graph Theory , pp. 56 - 72
Publisher: Cambridge University Press
Print publication year: 2015

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. J. E., Bartels and D., Welsh, The Markov chain of colourings, Proc. 4th International IPCO Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 920, Springer-Verlag (1995), 373–387.Google Scholar
2. N. L., Biggs, R. M., Damerell and D. A., Sands, Recursive families of graphs, J. Combin. Theory (B) 12 (1972), 123–131.Google Scholar
3. G. D., Birkhoff, A determinant formula for the number of ways of colouring a map, Ann. of Math. 14 (1912), 42–46.Google Scholar
4. G. D., Birkhoff and D. C., Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355–451.Google Scholar
5. A., Bohn, Chromatic roots as algebraic integers, DMTCS Proceedings, North America, July 2012, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAR0148/ 3962.
6. A., Bohn, Chromatic polynomials of complements of bipartite graphs, Graphs Combin. 30 (2014), 287–301.Google Scholar
7. A., Bohn, A dense set of chromatic roots which is closed under multiplication by positive integers, Discrete Math. 321 (2014), 45–52.Google Scholar
8. F., Brenti, Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc. 332 (1992), 729–756.Google Scholar
9. P. J., Cameron and K., Morgan, Algebraic properties of chromatic roots, submitted.
10. F. M., Dong, Proof of a chromatic polynomial conjecture, J. Combin. Theory (B) 78 (2000), 35–44.Google Scholar
11. F. M., Dong and B., Jackson, A zero-free interval for chromatic polynomials of nearly 3-connected plane graphs, SIAM J. Discrete Math. 25 (2011), 1103–1118.Google Scholar
12. F. M., Dong and K. M., Koh, Bounds for the real zeros of chromatic polynomials, Combin. Probab. Comput. 17 (2008), 749–759.Google Scholar
13. F. M., Dong and K. M., Koh, On zero-free intervals in (1, 2) of chromatic polynomials of some families of graphs, SIAM J. Discrete Math. 24 (2010), 370–378.Google Scholar
14. F. M., Dong, K. M., Koh and K. L., Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific Publishing Co., 2005.Google Scholar
15. H., Edwards, R., Hierons and B., Jackson, The zero-free intervals for characteristic polynomials of matroids, Combin. Probab. Comput. 7 (1998), 153–165.Google Scholar
16. L. A., Goldberg and M., Jerrum, The complexity of computing the sign of the Tutte polynomial (and consequent #P-hardness of approximation), http://arxiv.org/abs/1104.0707v4.
17. S., Fadnavis, On Brenti's conjecture about the log-concavity of the chromatic polynomial, Europ. J. Combin. 33 (2012), 1842–1846.Google Scholar
18. S., Fadnavis, A generalization of the birthday problem and the chromatic polynomial, http://arxiv. org/abs/1105.0698v2.
19. G. E., Farr, Tutte–Whitney polynomials: some history and generalizations, Combinatorics, Complexity, and Chance, Oxford Lecture Ser. Math. Appl. 34, Oxford University Press (2007), 28–52.Google Scholar
20. R., Fernández and A., Procacci, Cluster expansion for abstract polymer models: new bounds from an old approach, Comm. Math. Phys. 274 (2007), 123–140.Google Scholar
21. R., Fernández and A., Procacci, Regions without complex zeros for chromatic polynomials on graphs with bounded degree, Combin. Probab. Comput. 17 (2008), 225–238.Google Scholar
22. C. M., Fortuin and P. W., Kasteleyn, On the random-cluster model. I. Introduction and relation to other models, Physica 57 (1972), 536–564.Google Scholar
23. J., Huh, Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, J. Amer. Math. Soc. 25 (2012), 907–927.Google Scholar
24. B., Jackson, A zero-free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2 (1993), 325–336.Google Scholar
25. B., Jackson, Zeros of chromatic and flow polynomials of graphs, J. Geometry 76 (2003), 95–109.Google Scholar
26. B., Jackson, A zero-free interval for flow polynomials of cubic graphs, J. Combin. Theory (B) 97 (2007), 127–143.Google Scholar
27. B., Jackson, Zero-free intervals for flow polynomials of near cubic graphs, Combin. Probab. Comput. 16 (2007), 85–108.Google Scholar
28. B., Jackson, Counting 2-connected deletion minors of binary matroids, Discrete Math. 313 (2013), 1262–1266.Google Scholar
29. B., Jackson and A. D., Sokal, Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids, J. Combin. Theory(B) 99 (2009), 869–903.Google Scholar
30. B., Jackson and A. D., Sokal, Maxmaxflow and counting subgraphs, Electron. J. Combin. 17 (2010), No. 1, Research Paper 99, 46 pp.Google Scholar
31. M., Kochol, Polynomials associated with nowhere zero flows, J. Combin. Theory (B) 84 (2002), 260–269.Google Scholar
32. R., Kotecký and D., Preiss, Cluster expansion for abstract polymer models, Comm. Math. Phys. 103 (1986), 491–498.Google Scholar
33. J. G., Oxley, On minor-minimally-connected matroids, Discrete Math. 51 (1984), 63–72.Google Scholar
34. J. G., Oxley, Matroid Theory (2nd edn.), Oxford University Press, 2011.Google Scholar
35. R. B., Potts, Some generalized order-disorder transformations, Proc. Cambridge Philos. Soc. 48 (1952), 106–109.Google Scholar
36. R. C., Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968), 52–71.Google Scholar
37. G. F., Royle, Recent results on chromatic and flow roots of graphs and matroids, Surveys in Combinatorics 2009 (eds. S., Huczynska, J. D., Mitchell and C. M., Roney-Dougal), Cambridge University Press (2009), 289–327.Google Scholar
38. P. D., Seymour, Two chromatic polynomial conjectures, J. Combin. Theory (B) 70 (1997), 184–196.Google Scholar
39. A. D., Sokal, Bounds on the complex zeros of (di)chromatic polynomials and Potts model partition functions, Combin. Probab. Comput. 10 (2001), 41–77.Google Scholar
40. A. D., Sokal, Chromatic roots are dense in the whole complex plane, Combin. Probab. Comput. 13 (2004), 221–261.Google Scholar
41. A. D., Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, Surveys in Combinatorics, 2005 (ed. B. S., Webb), Cambridge University Press (2005), 173–226.Google Scholar
42. C., Thomassen, On the number of hamiltonian cycles in bipartite graphs, Combin. Probab. Comput. 5 (1996), 437–442.Google Scholar
43. C., Thomassen, The zero-free intervals for chromatic polynomials of graphs, Combin. Probab. Comput. 6 (1997), 497–506.Google Scholar
44. C., Thomassen, Chromatic roots and hamiltonian paths, J. Combin. Theory (B) 80 (2000), 218–224.Google Scholar
45. W. T., Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80–91.Google Scholar
46. W. T., Tutte, On chromatic polynomials and the golden ratio, J. Combin. Theory (B) 9 (1970), 289–296.Google Scholar
47. W. T., Tutte, Chromials, Springer Lecture Notes in Math. 411 (1974), 243–266.Google Scholar
48. C. D., Wakelin, Chromatic Polynomials, Ph.D. thesis, University of Nottingham, 1994.Google Scholar
49. H., Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932), 572–579.Google Scholar
50. H., Whitney, The coloring of graphs, Ann. Math. 33 (1932), 688–718.Google Scholar
51. D. R., Woodall, Zeros of chromatic polynomials, Combinatorial Surveys (ed. P. J., Cameron), Academic Press (1977), 199–223.Google Scholar
52. D. R., Woodall, A zero-free interval for chromatic polynomials, DiscreteMath. 101 (1992), 333–341.Google Scholar
53. D. R., Woodall, The largest real zero of the chromatic polynomial, Discrete Math. 172 (1997), 141–153.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×