Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations
| Autor: | Dong, Fengming, Ge, Jun, Gong, Helin, Ning, Bo, Ouyang, Zhangdong, Tay, Eng Guan |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1002/jgt.22617 |
| Popis: | The chromatic polynomial $P(G,x)$ of a graph $G$ of order $n$ can be expressed as $\sum\limits_{i=1}^n(-1)^{n-i}a_{i}x^i$, where $a_i$ is interpreted as the number of broken-cycle free spanning subgraphs of $G$ with exactly $i$ components. The parameter $\epsilon(G)=\sum\limits_{i=1}^n (n-i)a_i/\sum\limits_{i=1}^n a_i$ 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\"{o}m in 2006 that $\epsilon(T_n)< \epsilon(G)<\epsilon(K_n)$ holds for any connected graph $G$ of order $n$ which is neither the complete graph $K_n$ nor a tree $T_n$ of order $n$. The most crucial step of our proof is to obtain the interpretation of all $a_i$'s by the number of acyclic orientations of $G$. Comment: 20 pages, 23 references. To appear in J. Graph Theory |
| Databáze: | arXiv |
| Externí odkaz: |
|