Real-rootedness of the $\tau$-polynomial under graph joins

Abstract

For a simple graph $G$ with $n$ vertices, write its chromatic polynomial in the rising factorial basis as $${\chi }_G(x)=\sum _{i=0}^n(-1{)}^{n-i}{c}_i(G)⟨x{⟩}_i,$$ where $⟨x{⟩}_i=x(x+1)\cdots (x+i-1).$ The associated $\tau$-polynomial $${\tau }_G(x)=\sum _{i=0}^n{c}_i(G)x^i$$ was defined and systematically investigated by Brenti in 1992. In this paper, we prove that if the $\tau$-polynomials of two vertex-disjoint simple graphs $G$ and $H$ have only real zeros, then the $\tau$-polynomial of their join $G\vee H$ has only real zeros. This settles a conjecture posed by Brenti, Royle and Wagner since 1994.

13 pages