Chromatic polynomials
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].
- Foundations of the chromatic polynomial
- Zeros of chromatic and flow polynomials of graphs
- scientific article; zbMATH DE number 2199828
- Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
- Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree
- Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
- A chromatic partition polynomial
- Zeros of chromatic and flow polynomials of graphs
- Polychromatic polynomials
- Chromatic polynomials and order ideals of monomials
- A matrix method for chromatic polynomials
- DP color functions versus chromatic polynomials
- Polynomials counting nowhere-zero chains in graphs
- Chromatic polynomial of intuitionistic fuzzy graphs using \(\left( \alpha, \beta\right)\)-levels
- Chromatic polynomials of mixed hypercycles
- Discrete chromatic series
- scientific article; zbMATH DE number 4181365 (Why is no real title available?)
- Orbital Chromatic and Flow Roots
- scientific article; zbMATH DE number 5356325 (Why is no real title available?)
- scientific article; zbMATH DE number 5626056 (Why is no real title available?)
- scientific article; zbMATH DE number 6928912 (Why is no real title available?)
- An introduction to the k-defect polynomials
- scientific article; zbMATH DE number 1390127 (Why is no real title available?)
- CHROMATIC POLYNOMIAL OF SEMI-UNIFORM HYPERSTAR
- Galois groups of chromatic polynomials
- scientific article; zbMATH DE number 2199828 (Why is no real title available?)
- scientific article; zbMATH DE number 5251073 (Why is no real title available?)
- scientific article; zbMATH DE number 6468926 (Why is no real title available?)
- Foundations of the chromatic polynomial
- An improved lower bound of P(G,L)-P(G,k) for k-assignments L
- DP color functions versus chromatic polynomials (II)
- Comparing list-color functions of uniform hypergraphs with their chromatic polynomials. II
- Chromatic polynomials of 2-edge-coloured graphs
- The amazing chromatic polynomial
- Benjamini-Schramm continuity of root moments of graph polynomials
- Gale duality bounds for roots of polynomials with nonnegative coefficients
This page was built for publication: Chromatic polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2822590)
