New expressions for order polynomials and chromatic polynomials

Abstract

Let $G=(V,E)$ be a simple graph with $V=\{1,2,\cdots ,n\}$ and $\chi (G,x)$ be its chromatic polynomial. For an ordering $\pi =(v_1,v_2,\cdots ,v_n)$ of elements of $V$, let ${\delta }_G(\pi )$ be the number of $i$'s, where $1\le i\le n-1$, with either $v_i<v_{i+1}$ or $v_i{v}_{i+1}\in E$. Let $\mathcal{W}(G)$ be the set of subsets $\{a,b,c\}$ of $V$, where $a<b<c$, which induces a subgraph with $ac$ as its only edge. We show that $\mathcal{W}(G)=\varnothing$ if and only if $(-1{)}^n\chi (G,-x)={\sum }_{\pi }(\genfrac{}{}{0ex}{}{x+{\delta }_G(\pi )}{n})$, where the sum runs over all $n!$ orderings $\pi$ of $V$. To prove this result, we establish an analogous result on order polynomials of posets and apply Stanley's work on the relation between chromatic polynomials and order polynomials.

33 pages and 5 figures. Will appear in JGT

References in corpus (1)

• Chromatic roots are dense in the whole complex plane