Divisibility of certain coefficients of the chromatic polynomials. (Q1420611)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Divisibility of certain coefficients of the chromatic polynomials. |
scientific article |
Statements
Divisibility of certain coefficients of the chromatic polynomials. (English)
0 references
2 February 2004
0 references
It is well known that the number of distinct \(\lambda\)-colorings of a graph \(G\) may be expressed as a polynomial \(\sum^ n_{i=1}(-1)^{n-i}a_ i(G)\lambda^ i\), called the chromatic polynomial of \(G\). \textit{Y.~Hong} [J. East China Norm. Univ., Nat. Sci. Ed. 1984, 33--35 (1984; Zbl 0576.05026)] showed that for any connected graph \(G\) with chromatic number \(\chi(G)\), \(a_1(G)\) is divisible by \((\chi(G)-1)!\) and moreover, \(G\) is bipartite iff \(a_1(G)\) is odd. The paper under review extends these results to those on the divisibility of \(a_i(G)\) for each \(i=1,2,\dots,\chi(G)-1\).
0 references
chromatic number
0 references
uniquely \(k\)-colorable graph
0 references