Chromatic polynomials (Q2822590)

Let \(G\) be a graph on \(n\) vertices. For any positive integer \(q\), the number \(P(G,q)\) is defined as the number of distinct proper \(q\)-colourings of \(G\). Then the chromatic polynomial of \(G\) is defined as the unique interpolating polynomial of degree at most \(n\) through the points \({ \left\{(0,P(G,0)),(1,P(G,1)),\dots ,(n,P(G,n))\right\}}.\)NEWLINENEWLINEIn the present chapter, basic examples are shown and some reduction techniques are presented. Also, an interpretation for the coefficients of chromatic polynomials is given.NEWLINENEWLINEA special section of the chapter is dedicated to the roots of chromatic polynomials. Some results which determine intervals on the real line that are free from chromatic roots are presented. Moreover, the result from Sokal is mentioned, which claims that there are no zero-free regions in the complex plane for the family of all graphs. In addition, some algebraic properties of chromatics roots are given.NEWLINENEWLINEFinally, other related polynomials are considered. These are the flow polynomial, characteristic polynomials of matroids, the Potts model partition function, and the Tutte polynomials. Work on chromatic polynomials has many interactions with mathematical physics, since the chromatic polynomial is a specialization of the Potts model partition function, which is used by mathematical physicists to study phase transitions.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].