scientific article; zbMATH DE number 4051660
[For the entire collection see Zbl 0608.00004.] In this paper the authors use the following expression of the chromatic polynomial of a connected graph G of order n: \[ P_ G(\lambda)=\sum^{n-1}_{i=1}a_ i\lambda (\lambda-1)^ i, \] where \(\lambda(\lambda-1)^ i\) is the chromatic polynomial of a tree of order \(i+1\). This form of the chromatic polynomial is called here the Tutte polynomial form and it appears to be more suited to computation for sparse graphs. It is proved that the coefficients in the Tutte polynomial form alternate in sign and the absolute value of the second coefficient in this form is the cycle rank (cyclomatic number) of G. Previously, \textit{E. G. Whitehead} and \textit{L.-C. Zhao} [J. Graph Theory 8, 371-377 (1984; Zbl 0551.05041)] have obtained that the power to which \(\lambda\)-1 is raised in the last nonzero term is the number of blocks in G. Finally, the Tutte polynomial form is obtained for special classes of graphs: cycles, cacti, k-trees, wheels and bipartite graphs \(K_{2,n}\).
- The chromatic polynomial of \(P_2\times P_n\) and \(C_3\times P_n\)
- An extension of the bivariate chromatic polynomial
- A bibliography on chromatic polynomials
- Divisibility of certain coefficients of the chromatic polynomials.
- Chromatic polynomials and order ideals of monomials
- DP color functions versus chromatic polynomials
- Reflection on the coloring and chromatic numbers
- Some corollaries of a theorem of Whitney on the chromatic polynomial
- A Hodge decomposition interpretation for the coefficients of the chromatic polynomial
- 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 3920500 (Why is no real title available?)
- A note on the conditional chromatic polynomial
- scientific article; zbMATH DE number 697169 (Why is no real title available?)
- The two-variable chromatic polynomial of regular tree study
- scientific article; zbMATH DE number 5251073 (Why is no real title available?)
- DP color functions versus chromatic polynomials (II)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3788032)