Premium
Chromatic polynomials and σ‐polynomials
Author(s) -
Wakelin C. D.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199608)22:4<367::aid-jgt10>3.0.co;2-c
Subject(s) - chromatic polynomial , mathematics , combinatorics , chromatic scale , windmill graph , multipartite , discrete mathematics , graph , foster graph , midpoint , line graph , voltage graph , physics , geometry , quantum mechanics , quantum entanglement , quantum
In this paper we present some results on the sequence of coefficients of the chromatic polynomial of a graph relative to the complete graph basis, that is, when it is expressed as the sum of the chromatic polynomials of complete graphs. These coefficients are the coefficients of what is often called the σ‐polynomial. We obtain necessary and sufficient conditions for this sequence to be symmetrical, and we prove that it is ‘skewed’ and decreasing beyond its midpoint. We also prove that it is strongly log‐concave when G is a complete multipartite graph. © 1996 John Wiley & Sons, Inc.