scientific article; zbMATH DE number 4051660

From MaRDI portal
Publication:3788032





[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}\).











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)