1. Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations.
- Author
-
Dong, Fengming, Ge, Jun, Gong, Helin, Ning, Bo, Ouyang, Zhangdong, and Tay, Eng Guan
- Subjects
CHROMATIC polynomial ,GRAPH connectivity ,LOGICAL prediction ,ACYCLIC model ,COMPLETE graphs ,SUBGRAPHS ,COUNTING - Abstract
The chromatic polynomial P(G,x) of a graph G of order n can be expressed as ∑i=1n(−1)n−iaixi, where ai is interpreted as the number of broken‐cycle‐free spanning subgraphs of G with exactly i components. The parameter ϵ(G)=∑i=1n(n−i)ai∕∑i=1nai is the mean size of a broken‐cycle‐free spanning subgraph of G. In this article, we confirm and strengthen a conjecture proposed by Lundow and Markström in 2006 that ϵ(Tn)<ϵ(G)<ϵ(Kn) holds for any connected graph G of order n which is neither the complete graph Kn nor a tree Tn of order n. The most crucial step of our proof is to obtain the interpretation of all ai's by the number of acyclic orientations of G. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF