Expansions of chromatic polynomials and log-concavity

by

Francesco Brenti^{1} Department of Mathematics University of Michigan Ann Arbor, Michigan 48109-1003 U.S.A.

Abstract

In this paper we present several results and open problems about logconcavity properties of sequences associated with graph colorings. Five polynomials intimately related to the chromatic polynomial of a graph are introduced and their zeros, combinatorial and log-concavity properties are studied. Four of these polynomials have never been considered before in the literature and some yield new expansions for the chromatic polynomial.

1 Introduction

Log-concave and unimodal sequences arise often in combinatorics, algebra, geometry and computer science, as well as in probability and statistics where these concepts were first defined and studied (see, [2], for further information and references about the origin of the concept of a unimodal sequence). Even though log-concavity and unimodality have one-line definitions, it has now become apparent that to prove the unimodality or log-concavity of a sequence can sometimes be a very difficult task requiring the use of intricate combinatorial constructions ([40], [58], [32], [62]) or of refined mathematical tools. The number and variety of these tools has been constantly increasing and is quite bewildering and surprising. They include, for example, classical analysis ([54], [55], and [56]), linear algebra ([35]), the representation theory of Lie algebras and superalgebras ([34], [46], and [47]), the theory of total positivity ([8], [9], and [11]), the theory of symmetric functions ([10], [13], and [41]), and algebraic geometry ([49]). We refer the interested reader to [50] for an excellent survey of many of these techniques, problems, and results.

1Partially supported by NSF grant # DMS 8903246

In this paper we use the theory of total positivity and analytical results to study some remarkable log-concavity properties arising from the enumeration of colorings of a graph. More precisely, we will consider the zeros and the log-concavity properties of the chromatic polynomial of a graph and of five other polynomials naturally associated with it. Zeros and log-concavity properties of chromatic polynomials have been studied for several years (see, e.g., [1], [20], [38], [53], [60]) and one of the other five polynomials, the σ-polynomial, has been considered before in the literature (see [15], [29], [30], and [61]), though none of these authors studied its logconcavity properties. The other four polynomials, however, have never appeared before. In this work we show that all these polynomials possess interesting logconcavity properties and that many previously known results about chromatic and σ-polynomials can be interpreted as log-concavity results. We also present several open problems and conjectures.

The organization of the paper is as follows. In the next section we recall some definitions, notation, and results that will be used for the rest of the paper, as well as two fundamental analytical results that are the theoretical foundation of all the results that follow. In §3 we study the zeros and log-concavity properties of the σ-polynomial and of the augmented σ-polynomial of a graph. We prove that these polynomials are log-concave or have only real zeros for many general classes of graphs such as, for example, complements of comparability and triangle-free graphs, graphs with a high chromatic number, interval graphs, board graphs, triangulated graphs, complete multipartite graphs, and trees. We also prove that the property of the σpolynomial having only real zeros is preserved under an operation of “composition” of graphs which includes the ordinary product and disjoint union of two graphs. In §4 we study the w-polynomial of a graph. After giving a combinatorial interpretation of its coefficients (which yields a new expansion for the chromatic polynomial of a graph, Theorem 4.4) we prove that the w-polynomial has only real zeros for a general class of graphs which strictly includes the chordal graphs. We also prove that the reality of the zeros of the w-polynomial is preserved under the operation of disjoint union, and we discuss the relationships between the zeros of the w-polynomial and those of the σ and augmented σ-polynomial. In §5 we introduce and study the τ and augmented τ-polynomial of a graph and discuss the connections between its zeros and log-concavity properties and those of the polynomials considered in §3 and §4. A simple combinatorial interpretation is found for the coefficients of the τ-polynomial which yields another new expansion of the chromatic polynomial of a graph (Theorem 5.5) and also generalizes a result of R. Stanley. In §6 we look at the log-concavity properties of the chromatic polynomial itself and we relate them to corresponding properties of the other five polynomials considered in this paper. Finally, in §7, we discuss some of the main open problems arising from our work and present some conjectures.

2 Notation and Preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this paper. We let P =^{def} {1, 2, 3, …} and N =^{def} P ∪ {0}; for a ∈ N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). The cardinality of a set A will be denoted by |A|. A sequence {a_{0}, a_{1}, …, a_{d}} (of real numbers) is called log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d − 1. It is said to be unimodal if there exists an index 0 ≤ j ≤ d such that a_{i} ≤ a_{i+1} for i = 0, …, j − 1 and a_{i} ≥ a_{i+1} for i = j, …, d − 1. It is said to have no internal zeros if there are not three indices 0 ≤ i < j < k ≤ d such that a_{i}, a_{k} ≠ 0 and a_{j} = 0. We say that a polynomial ∑_{i=0}^{d} a_{i} x^{i} is log-concave (respectively, unimodal, with no internal zeros) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known that if ∑_{i=0}^{d} a_{i} t^{i} is a polynomial with nonnegative coefficients and with only real zeros, then the sequence {a_{0}, a_{1}, …, a_{d}} is log-concave and unimodal, with no internal zeros (see, e.g., [9], or [14], Thm. B, p.270).

We will denote by K_{p} (respectively, C_{p} and N_{p}), the complete graph (respectively, the cycle, and the empty graph) on p vertices, and by K_{p_{1},...,p_{n}} the complete multipartite graph on p_{1}, …, p_{n} vertices. Given a graph G we will denote by χ(G; x) its chromatic polynomial, by ν(G) its chromatic number, and by k G (where k ∈ P) the graph consisting of k disjoint copies of G. Given two graphs G and H we denote by G ⊎ H the disjoint union of G and H. Given a graph G = (V, E) a walk in G is a sequence v_{0}v_{1} … v_{n} of vertices of G such that (v_{i}, v_{i+1}) ∈ E for i = 0, …, n − 1, the integer n is called the length of the walk, and the walk is called closed if v_{0} = v_{n}. A closed walk v_{0}v_{1} … v_{n} is called a cycle if the vertices v_{0}v_{1} … v_{n−1} are all distinct. A chord of a cycle v_{0}v_{1} … v_{n} is an edge of the form (v_{i}, v_{j}) where 0 ≤ i < j ≤ n − 1 and j − i ≥ 2. For other graph theoretic notation and terminology we will follow [7].

By a simplicial complex we will mean a collection of sets F with the property that if A ∈ F and B ⊆ A then B ∈ F. We call the elements of F the faces of F. For S ∈ F, the dimension of S is |S| − 1. Two general classes of simplicial complexes will be particularly important for us. Given a partially ordered set (or, poset, for short) P we let Δ(P) be the simplicial complex of all the chains (i.e. totally ordered subsets) of P. We call Δ(P) the order complex of the poset P. Given a graph G = (V, E) we let I(G) be the simplicial complex of all the independent subsets of V, and we call I(G) the independence complex of the graph G.

Given p ∈ P, we will often use the basis of the vector space V_{p} of real polynomials of degree ≤ p consisting of the polynomials \{(\begin{matrix}x+p−i \\ p \end{matrix})\}_{i=0,...,p}. It is not hard to see that these polynomials are indeed a basis of V_{p} (see, e.g., [48], p.209). The reason why this basis is often used in enumerative combinatorics lies in the following result which is, essentially, a restatement of the binomial theorem (see, e.g., [48], p.16). Theorem 2.1: Let A(x) be a real polynomial of degree d. Then

A(x) = ∑_{i=0}^{d} b_{i} (\begin{matrix}x+d−i \\ d \end{matrix})

if and only if

∑_{n≥0} A(n) x^{n} = \frac{∑_{i=0}^{d}b_{i} x^{i}}{(1 − x)^{d+1}} ,

as formal power series.

A proof of the preceding result can be found in [9], Thm.2.3.3. Since we will be often dealing with polynomials having only real zeros it will be convenient to introduce the following terminology. Given two polynomials f and g having only real zeros we say that g interlaces f if deg (g) = deg (f) − 1 and we have that

η_{1} ≤ ξ_{1} ≤ η_{2} ≤ … ≤ η_{d−1} ≤ ξ_{d−1} ≤ η_{d}

where η_{1}, η_{2}, …, η_{d} are the zeros of f and ξ_{1}, ξ_{2}, …, ξ_{d−1} are those of g. Given a polynomial f having only real zeros we denote by λ(f) (respectively Λ(f)) the smallest (respectively the largest) zero of f.

We now recall two analytical results that relate the basis \{(\begin{matrix}x+p−i \\ p \end{matrix})\}_{i=0,...,p} with polynomials having only real zeros. They are fundamental for this paper. Theorem 2.2: Let

A(x) = ∑_{i=0}^{d} b_{i} (\begin{matrix}x+d−i \\ d \end{matrix})

be a polynomial of degree d. Suppose that A(x) has only real zeros and that A(x) = 0 for all x ∈ ([λ(A), −1] ∪ [0, Λ(A)]) ∩ Z . Then the polynomial ∑_{i=0}^{d} b_{i} x^{i} has only real zeros. Theorem 2.3: Let ∑_{i=0}^{p} a_{i} x^{i} and ∑_{i=0}^{q} b_{i} x^{i} be two polynomials with only real zeros and nonnegative coefficients. Define a sequence {c_{0}, c_{1}, …, c_{p+q}} by

∑_{i=0}^{p+q} c_{i} (\begin{matrix}x+p+q−i \\ p+q \end{matrix}) =^{def} (∑_{i=0}^{p} a_{i} (\begin{matrix}x+p−i \\ p \end{matrix}) ) (∑_{i=0}^{q} b_{i} (\begin{matrix}x+q−i \\ q \end{matrix}) );

then the polynomial ∑_{i=0}^{p+q} c_{i} x^{i} has only real zeros and nonnegative coefficients.

We state below two equivalent formulations of Theorem 2.3 that are completely independent from the polynomials (\begin{matrix}x+p−i \\ p \end{matrix}). Theorem 2.4: Let V (z) and U(z) be two polynomials of degrees ≤ a and ≤ b, respectively, having only real zeros and nonnegative coefficients. Define a polynomial W (z) by

W (z) =^{def} (1 − z)^{a+b+1} [(\frac{d}{dx})^{b} [\frac{V (x) U (\frac{z}{x}) x^{b}}{(1 − x)^{a+1}} ]]_{|x=z} .

Then W (z) has only real zeros and nonnegative coefficients. Theorem 2.5: Let U(z) and V (z) be two polynomials having nonnegative coefficients and all their zeros in the interval [−1, 0]. Define a polynomial W (z) by

W (z) =^{def} ∑_{i∈N} \frac{(z + 1)^{i} z^{i}}{(i!)^{2}} (\frac{d}{dz} )^{i} (V (z)) (\frac{d}{dz} )^{i} (U(z)) .

Then W (z) has (nonnegative coefficients and) all its zeros in the interval [−1, 0].

The equivalence of Theorems 2.4 and 2.3 is proved in [9], Thm. 4.7.4, while the equivalence of Theorems 2.5 and 2.3 is proved in [54] (see Lemma 1.2.2 and Thm. 1.4.4). Theorems 2.2 and 2.5 are both highly non-trivial results and we refer the reader to [9], Thm.4.4.1, and [56], Thm.2.15, respectively, for their proofs.

3 The σ-polynomial

Let G be a graph on p vertices and let

χ(G; x) = ∑_{i=0}^{p} a_{i} (x)_{i}  (1)

be its chromatic polynomial, where (x)_{i} =^{def} x (x − 1) … (x − i + 1) for i ≥ 1, and (x)_{0} =^{def} 1. We define the σ-polynomial of G to be the polynomial defined by

σ(G; x) =^{def} ∑_{i=0}^{p} a_{i} x^{i}.  (2)

The σ-polynomial was first explicitly defined and studied by Korfhage in 1978 (see [29]), though, actually, his definition of the σ-polynomial is equivalent to what we denote by σ(G; x)/x^{ν(G)}. However, since all the properties that we are going to consider in this work hold for σ(G; x)/x^{ν(G)} if and only if they hold for σ(G; x), this difference is immaterial.

We begin by “rewriting” in terms of σ-polynomials the following elementary and well known result about chromatic polynomials. It can also be proved directly from (1) using the combinatorial interpretation of χ(G; x). Recall that a partition of a (finite) set V is a collection π = {B_{1}, …, B_{k}} of mutually disjoint subsets of V such that ⋃_{i=1}^{k} B_{i} = V. We call the elements of π the blocks of π. Theorem 3.1: Let G = (V, E) be a graph with p vertices and q edges and let (2) be its σ-polynomial. Then, for i = 0, …, p, a_{i} equals the number of partitions of V into exactly i independent sets. In particular a_{p} = 1, a_{p−1} = (\begin{matrix}p \\ 2 \end{matrix}) − q, a_{i} = 0 for i = 0, …, ν(G) − 1, and a_{i} > 0 if i = ν(G), …, p. □

It is also possible to give an explicit formula for the coefficient of x^{p−2} in σ(G; x). The following result first appeared (though stated and proved incorrectly) in [15], p.220. Proposition 3.2: Let G = (V, E) be a graph with p vertices and q edges and let (2) be its σ-polynomial. Then

a_{p−2} = (\begin{matrix}q \\ 2 \end{matrix}) − q (\begin{matrix}p − 1 \\ 2 \end{matrix}) + (\begin{matrix}p \\ 3 \end{matrix}) (\frac{3p − 5}{4}) − t(G) ,  (3)

where t(G) is the number of triangles of G. Proof: Let

χ(G; x) = ∑_{i=0}^{p}(−1)^{p−i} b_{i} x^{i}  (4)

be the chromatic polynomial of G. It then follows from (1), (4), and a well known identity (see, e.g., [48], p.35), that

a_{p−2} = b_{p−2} − S(p − 1, p − 2) b_{p−1} + b_{p} S(p, p − 2) ,  (5)

where S(p, k) is the number of partitions of [p] into exactly k blocks (see, e.g., [48], p.33 for further information about the S(p, k)’s). Now, it follows easily from this combinatorial interpretation that

S(p − 1, p − 2) = (\begin{matrix}p−1 \\ 2 \end{matrix})  (6)

and that

S(p, p − 2) = \frac{1}{2} (\begin{matrix}p \\ 2,2,p−4 \end{matrix}) + (\begin{matrix}p \\ 3 \end{matrix}) .  (7)

Substituting now (6) and (7) in (5) and using the well known facts that b_{p} = 1, b_{p−1} = q and b_{p−2} = (\begin{matrix}q \\ 2 \end{matrix}) − t(G) (see, e.g., [36], Theorem 16), gives (3), as desired. □

In order to prove the next result it will be necessary to define a polynomial that was first introduced and studied in [55]. Let V be a finite set. A collection F of subsets of V is called a set system on V if ∅ ∈ F and ⋃_{X∈F}X = V. Given a set system F on V we define the partition polynomial of F by

ρ(F; x) =^{def} ∑_{k≥0} p_{k}(F) x^{k} ,  (8)

where p_{k}(F) equals the number of partitions of V into k blocks such that each block is in F. It follows immediately from (2) and Theorem 3.1 that, if I(G) is the independence complex of a graph G, then

ρ(I(G); x) = σ(G; x).  (9)

Thus the partition polynomial of a set system is a generalization of the σ-polynomial of a graph. Indeed, the partition polynomial of a set system possesses many other interesting properties as well (such as, for example, that of being also a generalization of the matching polynomial of a graph) and we refer the interested reader to [55] for further information about it.

We can now prove one of the main results of this section. Recall that a graph G = (V, E) is called a comparability graph (see, e.g., [21], p. 539) if there exists a partial order ⪯ on V such that (x, y) ∈ E if and only if x ≠ y and either x ⪯ y or y ⪯ x. Theorem 3.3: Let G be a graph such that the complementary graph G^{c} is a comparability graph. Then σ(G; x) has only real zeros. Proof: Since G^{c} is a comparability graph there exists a partially ordered set P = (V, ⪯), on V, such that (x, y) ∉ E if and only if x ≠ y and x and y are comparable in P. Therefore a subset S ⊆ V is independent in G if and only if it is a chain of P. Hence I(G) is the order complex of P. But, by Thm.2.5 of [55] the partition polynomial of an order complex has only real nonpositive zeros. Hence ρ(I(G); x) has only real zeros and the result follows from (9). □

Using a well known characterization of comparability graphs (Thm.1 of [21]) we can restate Theorem 3.3 in the following form. Recall (see, e.g, [21], p.539) that a triangular chord of a closed walk v_{0}v_{1} … v_{n} is an edge of the form (v_{i}, v_{i+2}), (where

0 ≤ i ≤ n − 1 and v_{j} =^{def} v_{j−n} if j > n).

Theorem 3.4: Let G be a graph such that each closed walk of odd length of G^{c} has at least one triangular chord. Then σ(G; x) has only real zeros. □

Theorems 3.3 and 3.4 have quite a large applicability. For example, as immediate consequences of them, we obtain the following results. (We refer the reader to, e.g., [21], p. 539, for the definition of an interval graph.) Corollary 3.5: Let G be an interval graph. Then σ(G; x) has only real zeros. Proof: Since G is an interval graph there follows from Thm. 2 of [21] that every closed walk of odd length of G^{c} has at least one triangular chord and the thesis follows from Theorem 3.4. □ Corollary 3.6: Let N_{p} be the empty graph on p vertices. Then σ(N_{p}; x) has only real zeros. □

Note that Corollary 3.6 is equivalent (by Theorem 3.1) to the known (see, e.g., [14], Thm. D, p. 271), but not trivial fact that the polynomial

∑_{i=0}^{p} S(p, i) x^{i}

has only real zeros, where S(p, i) has the same meaning as in the proof of Proposition 3.2. Therefore Theorem 3.3 is a generalization of this well known result.

Another general class of graphs for which σ(G; x) has only real zeros consists of all the graphs G = (V, E) such that ν(G) ≥ |V | − 2. Before we can prove this result, however, we need to define two infinite families of graphs. Let t, m, n ∈ N, following [18] we let V (t, m, n) be the graph obtained from two (disjoint) stars K_{1,t+n} and K_{1,t+m} by identifying t of their leaves and we let T (t, m, n) be the graph obtained from V (t, m, n) by adding the edge that connects the two centers of the stars. So, for example, the graphs V (4, 2, 1) and T (2, 2, 1), are shown in Figures 1 and 2, respectively (the meaning of the orientation of the edges of V (4, 2, 1) and T (2, 2, 1) is given in the proof of Theorem 3.8). The following result appears in [18], Thm.2.2, and we refer the reader to this source for its proof.

[figure]

Figure 1: The graph V (4, 2, 1)

[figure]

Figure 2: The graph T (2, 2, 1)

Theorem 3.7: Let G be a graph on p vertices such that ν(G) ≥ p − 2. Then there exist k, t, m, n ∈ N such that one of the following three conditions is satisfied:

(i) G^{c} = C_{5} ⊎ k K_{1};

(ii) G^{c} = T (t, m, n) ⊎ k K_{1}; (iii) G^{c} = V (t, m, n) ⊎ k K_{1}.

Using the preceding theorem, we obtain the following consequence of Theorem 3.3. Theorem 3.8: Let G be a graph on p vertices such that ν(G) ≥ p−2. Then σ(G; x) has only real zeros. Proof: It is easy to see that, for all k, t, m, n ∈ N, the graphs T (t, m, n) ⊎ k K_{1}, and V (t, m, n) ⊎ k K_{1}, are comparability graphs (Figures 1 and 2 show the right orientations for V (4, 2, 1) and T (2, 2, 1), the general cases being completely analogous). On the other hand, it is not hard to verify directly that σ((C_{5} ⊎ k K_{1})^{c}; x) = σ((C_{5})^{c}; x) x^{k} = x^{k+3} (x^{2}+5x+5), which has only real zeros. The thesis then follows from Theorems 3.3 and 3.7. □

As an immediate consequence, we obtain the following inequality, which first appeared in [61], Thm.6. Theorem 3.9: Let G be a graph on p vertices with ν(G) ≥ p − 2 and let (2) be its σ-polynomial. Then

a_{p−1}^{2} ≥ 4a_{p−2}.□

Let now H be a graph on p vertices v_{1}, v_{2}, …, v_{p} and G_{1}, G_{2}, …, G_{p} be p graphs with disjoint vertex sets V_{1}, V_{2}, …, V_{p}. We define the composition of H with G_{1}, …, G_{p}, denoted by H[G_{1}, …, G_{p}], to be the graph that has V =^{def} V_{1} ∪ V_{2} ∪ … ∪ V_{p} as vertex set and in which two vertices u, v ∈ V are adjacent if and only if either u, v ∈ V_{i} and (u, v) is an edge of G_{i}, for some 1 ≤ i ≤ p; or u ∈ V_{i}, v ∈ V_{j}, and (v_{i}, v_{j}) is an edge of H, for some 1 ≤ i, j ≤ p, i ≠ j. To the best of our knowledge, this operation of composition of graphs is new. It is, however, closely related to the operation of composition of set systems, which was first defined in [55], §4, which is, in turn, derived from a natural transformation in the theory of species (see [27]). Note that K_{2}[G_{1}, G_{2}] is just the ordinary product G_{1} ∘ G_{2} (as defined, e.g., in [3], p.60, or [36], p.60), and that N_{p}[G_{1}, G_{2}, …, G_{p}] is just the disjoint union G_{1} ⊎ G_{2} ⊎ G_{3} ⊎ … ⊎ G_{p}. We should also mention that the graphs H[K_{m_{1}}, …, K_{m_{p}}] have been studied in [37] where they are called “clan graphs with underlying graph H”. We are now ready to prove the second main result of this section. Theorem 3.10: Let H be a graph on p vertices and G_{1}, …, G_{p} graphs with disjoint vertex sets. Suppose that σ(G_{1}; x), …, σ(G_{p}; x) all have only real zeros and that H^{c} is triangle-free. Then σ(H[G_{1}, …, G_{p}]; x) has only real zeros.

Proof: With the notation above let S ⊆ V_{1} ∪ … ∪ V_{p}. Then it follows easily from our definitions that S ∈ I(H[G_{1}, …, G_{p}]) if and only if S ∩ V_{i} ∈ I(G_{i}) for i = 1, …, p, and {v_{i} : i ∈ [p], S ∩ V_{i} ≠ ∅} ∈ I(H). This means, in the terminology of [55], §4, that I(H[G_{1}, …, G_{p}]) is the composition of I(H) with I(G_{1}), …, I(G_{p}), as set systems. Now, since H^{c} is triangle-free, I(H) is a one-dimensional simplicial complex. Furthermore, it follows from (9) and from our hypotheses that ρ(I(G_{1}); x), …, ρ(I(G_{p}); x) all have only real nonpositive zeros. These conditions, by Thm.4.5 of [55], imply that ρ(I(H[G_{1}, … G_{p}]); x) has only real zeros, which, by (9), implies the desired result. □

In particular, we obtain the following result. Corollary 3.11: Let H be a graph such that H^{c} is triangle-free. Then σ(H; x) has only real zeros. □

Note that (H[G_{1}, …, G_{p}])^{c} may not be triangle-free even if H^{c} and G_{1}^{c}, …, G_{p}^{c} are (take, e.g., N_{2}[N_{2}, N_{1}]). Therefore Corollary 3.11 actually applies to a much wider class than just that of triangle-free graphs. In fact, it would be quite interesting to have a characterization of this class.

Theorem 3.10 is a tool for constructing graphs whose σ-polynomial has only real zeros. As an application, we have the following result. Theorem 3.12: Let G and H be two graphs such that σ(G; x) and σ(H; x) have only real zeros. Then σ(G ⊎ H; x) has only real zeros. Proof: As was observed above, G ⊎ H = N_{2}[G, H] and since (N_{2})^{c} is triangle-free the result follows from Theorem 3.10. □

For the operation of product of two graphs even more is true. The following is a well known result though it’s never been stated before in terms of σ-polynomials. Theorem 3.13: Let G_{1}, G_{2} be two graphs and let G_{1} ∘ G_{2} be their product. Then

σ(G_{1} ∘ G_{2}; x) = σ(G_{1}; x) σ(G_{2}; x) ;

in particular, σ(G_{1} ∘ G_{2}; x) has only real zeros if and only if both σ(G_{1}; x) and σ(G_{2}; x) have only real zeros. Proof: The result follows immediately from our definition (2) and Theorem 3.1. □

Two immediate corollaries of Theorem 3.13 are given below. Recall (see, e.g., [3], p.60) that the cone (respectively, suspension) of a graph G is the graph c(G) =^{def} N_{1}∘G (respectively, s(G) =^{def} N_{2} ∘ G). Corollary 3.14: Let G be a graph. Then the following are equivalent:

(i) σ(G; x) has only real zeros;

(ii) σ(c(G); x) has only real zeros;

(iii) σ(s(G); x) has only real zeros. □

Corollary 3.15: Let G be a complete multipartite graph. Then σ(G; x) has only real zeros. Proof: Let G = K_{m_{1},...,m_{r}}, then it is well known that K_{m_{1},...,m_{r}} = N_{m_{1}} ∘ … ∘ N_{m_{r}}. The thesis now follows from Theorem 3.13 and Corollary 3.6.□

A particularly elegant special case of the preceding result is the following. Corollary 3.16: Let H_{m} be the hyperoctahedral graph on 2m vertices. Then

σ(H_{m}; x) = x^{m} (x + 1)^{m};

in particular, σ(H_{m}; x) has only real zeros. Proof: By definition H_{m} = K^{2,2,...,2}_{m}. Hence, by Theorem 3.13,

σ(H_{m}; x) = σ(\underbrace{N_{2} ∘ … ∘ N_{2}}_{m}; x) = σ(N_{2}; x)^{m} ,

and the result follows. □

Using the definition (2) of the σ-polynomial we immediately obtain the following consequence of Corollary 3.16. Corollary 3.17: Let H_{m} be the hyperoctahedral graph on 2m vertices. Then

χ(H_{m}; x) = ∑_{i=0}^{m} ( \begin{matrix}m \\ i \end{matrix}) (x)_{m+i} .□

The preceding formula for the chromatic polynomial of an hyperoctahedral graph seems to be new and solves the recurrence relation obtained in [3], §9B, p.62, for the χ(H_{m}; x)’s.

There is another general class of graphs whose σ-polynomials have only real zeros. To describe it we need a few definitions. A board is a finite subset B ⊆ P×P. Let n, c, r ∈ P be such that B ⊆ [c] × [r] and n ≥ c. The rook polynomial and the n-factorial polynomial of B are the polynomials defined by

R(x; B) =^{def} ∑_{S∈R(B)} x^{|S|} ,  (10)

and

p_{n}(x; B) =^{def} ∑_{S∈R(B)}(x)_{n−|S|} ,  (11)

respectively, where R(B) =^{def} {S ⊆ B : (i_{1}, j_{1}), (i_{2}, j_{2}) ∈ S ⇒ i_{1} ≠ i_{2} , j_{1} ≠ j_{2}}.

These polynomials were first defined in [23] and have been extensively studied (see, e.g., [17], [23], and [24]). Following [24], §II, we call a graph G a board graph if there exist n ∈ P and a board B ⊆ [n] × P such that p_{n}(x; B) = χ(G; x). We can now prove the following result. Theorem 3.18: Let G be a board graph. Then σ(G; x) has only real zeros. Proof: Let n ∈ P and B ⊆ [n] × P be a board such that p_{n}(x; B) = χ(G; x) . By (1), (2), (10), and (11) this means that

σ(G; x) = x^{n} R (\frac{1}{x}; B) .  (12)

But it is known (see, [31], Thm.1) that the rook polynomial of any board has only real zeros, and the thesis follows. □

We should remark that, as noted in [24], p.140, no characterization of board graphs seems to be known.

There is one more operation on graphs which preserves the property of the σpolynomial having only real zeros. Before we can prove this, however, we need the following analytical result. Theorem 3.19: Let ∑_{i=0}^{d} a_{i} x^{i} be a polynomial having only real nonpositive zeros, and let

∑_{i=0}^{d+1} b_{i} (x)_{i} =^{def} (x − c) ∑_{i=0}^{d} a_{i} (x)_{i}  (13)

where c ≥ 0. Then ∑_{i=0}^{d+1} b_{i} x^{i} has only real zeros. Proof: It follows from (13) that

∑_{i=0}^{d+1} b_{i} (x)_{i} = ∑_{i=0}^{d} a_{i}[(x)_{i+1} + (i − c)(x)_{i}]
= ∑_{i=0}^{d+1}(a_{i−1} + a_{i}(i − c)) (x)_{i}

(where a_{−1} =^{def} a_{d+1} =^{def} 0) and hence that

∑_{i=0}^{d+1} b_{i} x^{i} = (x − c) A(x) + x A′(x) ,  (14)

where A(x) =^{def} ∑_{i=0}^{d} a_{i} x^{i}. By our hypothesis, A(x) has only real nonpositive zeros. Therefore A′(x) has only real zeros and interlaces A(x). Hence x A′(x) interlaces (x − c) A(x) and this, by a standard argument (see, e.g., [55], Lemma 1.3) implies that (x−c) A(x)+x A′(x) has only real zeros which, by (14), is the desired result. □

Let now G = (V, E) be a graph, v ∈ V, and n ∈ N. We denote by G_{v,n} the graph obtained from G by adding n new vertices u_{1}, …, u_{n} to V and adding all the edges (u_{i}, u_{j}) and (v, u_{i}) to E for 1 ≤ i, j ≤ n, i ≠ j. It will also be convenient to let G_{v,0} =^{def} G for any v ∈ V. Using the preceding theorem we can prove the following result. Theorem 3.20: Let G = (V, E) be a graph such that σ(G; x) has only real zeros. Then σ(G_{v,n}; x) has only real zeros for all v ∈ V and n ∈ N. Proof: By its definition, G_{v,n} is the union of G and of a complete graph on n + 1 vertices which “overlap” (in the sense of [36], p.59) on the vertex v. Hence

χ(G_{v,n}; x) = χ(G; x) (x − 1) … (x − n) .

Therefore

∑_{i=0}^{n+p} a_{i}(G_{v,n}) (x)_{i} = χ(G_{v,n}; x)
= (x − n) χ(G_{v,n−1}; x)
= (x − n) ∑_{i=0}^{p+n−1} a_{i} (G_{v,n−1}) (x)_{i}  (15)

where p =^{def} |V | and ∑_{i=0}^{n+p} a_{i} (G_{v,n}) x^{i} =^{def} σ(G_{v,n}; x). We are now done by induction and Theorem 3.19. □

As an immediate consequence of the preceding theorem we obtain the following result. Corollary 3.21: Let G be a tree. Then σ(G; x) has only real zeros. □

We close this section by introducing a modified version of the σ-polynomial which, besides giving rise to some interesting problems, “interpolates” between the σ-polynomial and the w-polynomial which will be introduced in the next section. Let G be a graph on p vertices and let (2) be its σ-polynomial. We define the augmented σ-polynomial of G by

\overline{σ}(G; x) =^{def} ∑_{i=0}^{p} i! a_{i} x^{i}.  (16)

As might be expected, the log-concavity properties and the zeros of the augmented σ-polynomial are related to those of the σ-polynomial. The two most important connections are given in the following two results. Theorem 3.22: Let G be a graph such that \overline{σ}(G; x) has only real zeros, then σ(G; x) has only real zeros. Theorem 3.23: Let G be a graph such that σ(G; x) has only real zeros, then \overline{σ}(G; x) is log-concave.

The preceding two Theorems follow from two purely analytical results appearing, e. g., in [9] (Thms.2.4.1 and 2.5.6, respectively) and we refer the reader to that source for their proofs. We also have the following result, whose easy verification is left to the reader. Proposition 3.24: Let G be a graph such that \overline{σ}(G; x) is log-concave. Then σ(G; x) is log-concave. □

By Theorem 3.23, many of the results in this section give rise to corresponding log-concavity results for \overline{σ}(G; x). However, the augmented σ-polynomial also gives rise to many open problems. For example, it would be interesting to know whether Theorems 3.10 and 3.13 have an analogue for augmented σ-polynomials and to know if Theorems 3.8, 3.18 and Corollaries 3.5, 3.11 remain valid when \overline{σ}(G; x) is substituted for σ(G; x), in their statements. Note, however, that not all of the results presented in this section about the zeros of σ(G; x) hold for \overline{σ}(G; x). For example, if G is the graph in Figure 3, then

[figure]

Figure 3

it is easy to see that the complementary graph G^{c} is a comparability graph. On the other hand, it is not hard to verify that

\overline{σ}(G; x) = 2x^{2} + 48x^{3} + 384x^{4} + 960x^{5} + 720x^{6},

which is easily seen not to have only real zeros. Therefore Theorems 3.3 and 3.4 do not hold for the augmented σ-polynomial. On the other hand, we will see in the next section that Corollaries 3.6, 3.21 and Theorems 3.12, 3.20 also hold for the augmented σ-polynomial, (see Corollaries 4.13, 4.14 and Theorems 4.17, 4.18).

4 The w-polynomial

Let G be a graph on p vertices and let

χ(G; x) = ∑_{i=0}^{p} w_{i} (\begin{matrix}x+p−i \\ p \end{matrix})  (17)

be its chromatic polynomial. The w-polynomial of G is the polynomial defined by

w(G; x) =^{def} ∑_{i=0}^{p} w_{i} x^{i}.  (18)

From Theorem 2.1 and our definition we immediately obtain the first important property of the w-polynomial. Proposition 4.1: Let G be a graph on p vertices and let w(G; x) be its w-polynomial. Then

∑_{n≥0} χ(G; n) x^{n} = \frac{w(G; x)}{(1 − x)^{p+1}} ,  (19)

(as formal power series).□

We now give a combinatorial interpretation to the coefficients of the w-polynomial. Let G = (V, E) be a graph on p vertices. An orientation of G is an assignment of a direction to each edge (u, v) ∈ E denoted by u → v or v → u. An orientation is said to be acyclic if it contains no directed cycles. We denote the set of all acyclic orientations of G by A(G). Given θ ∈ A(G) we can associate to it a finite poset P_{θ} having V as underlying set, and where, for x, y ∈ V, x ⪯ y in P_{θ} if and only if either x = y or there is a directed path from x to y in (G, θ). Given a finite poset P of cardinality p a linear extension of P (see, e.g., [48], p.110) is a bijection w : P → [p] such that x ⪯ y in P implies w(x) ≤ w(y) (as integers). We can now state our second result about the polynomial w(G; x). Recall that an ascent of a sequence (b_{1}, …, b_{n}) ∈ Z^{n} is an integer i ∈ [n − 1] such that b_{i} < b_{i+1}. We denote by a(b_{1}, …, b_{n}) the total number of ascents of (b_{1}, …, b_{n}). Theorem 4.2: Let G be a graph on p vertices and let w(G; x) be its w-polynomial. Then

w(G; x) = ∑_{θ∈A(G)} ∑_{σ:P_{θ}→[p]} x^{a(w_{θ}(σ^{−1}(1)),...,w_{θ}(σ^{−1}(p)))+1}  (20)

where P_{θ} is the poset associated to the acyclic orientation θ, w_{θ} : P_{θ} → [p] is (any) linear extension of P_{θ}, and σ runs over all linear extensions of P_{θ}.

Proof: It is proved in [44] (see eq.(1) on p.174) that given a graph G on p vertices we have that

χ(G; x) = ∑_{θ∈A(G)} \overline{Ω}(P_{θ}; x) ,  (21)

where \overline{Ω}(P_{θ}; x) is the strict order polynomial of the poset P_{θ} (see, e. g., [42], pp. 4 and 45, or [9], §1.2, for the definition of the strict order polynomial of a poset). But, for any poset P of size p, it is known (see [42], Props. 8.1, 8.2, and 8.3, p.24) that

∑_{n≥0} \overline{Ω}(P; n) x^{n} = \frac{∑_{σ:P →[p]}x^{a(w(σ^{−1}(1)),...,w(σ^{−1}(p)))+1}}{(1 − x)^{p+1}}  (22)

where w is (any) linear extension of P and σ runs over all linear extensions of P. Hence, since |P_{θ}| = p for all θ ∈ A(G), from (19), (21), and (22) we conclude that

∑_{n≥0} χ(G; n) x^{n} = \frac{∑_{θ∈A(G)} ∑_{σ:P_{θ}→[p]}x^{a(w_{θ}(σ^{−1}(1),...,w_{θ}(σ^{−1}(p)))+1}}{(1 − x)^{p+1}}  (23)

as formal power series in Z[[x]], where w_{θ} is (any) linear extension of P_{θ}. Comparing (23) with (19) yields the desired result. □

There is an equivalent way of stating Theorem 4.2 in purely graph theoretic terms which also has the advantage of showing that w(G; 1) = p!, a fact which is not obvious from (20). To do this we first need a definition. Let G = (V, E) be a graph on p vertices and assume (since we are dealing with labeled graphs) that V = [p]. Let now σ, τ ∈ S_{p} (where S_{p} denotes the symmetric group on p elements) we say that σ and τ are G-equivalent (denoted σ ≅_{G} τ) if for all (u, v) ∈ E we have that σ(u) < σ(v) ⇒ τ(u) < τ(v). It is easily verified that ≅_{G} is an equivalence relation which partitions S_{p} into a(G) =^{def} |A(G)| equivalence classes (note that this implies that a(G) = 1 if G has no edges). We can now state and prove the following equivalent formulation of Theorem 4.2. Theorem 4.3: Let G be a graph on p vertices. Then

w(G; x) = ∑_{i=1}^{a(G)} ∑_{τ∈S_{p}(σ_{i})} x^{a(σ_{i}∘τ^{−1})+1} ,  (24)

where S_{p}(σ) =^{def} {τ ∈ S_{p} : τ ≅_{G} σ}, and σ_{1}, …, σ_{a(G)} are a complete set of distinct representatives of S_{P} modulo ≅_{G}.

Proof: Let σ ∈ S_{p}. Define an orientation θ_{σ} in G by letting u → v in θ_{σ} if and only if σ(u) < σ(v). The orientation θ_{σ} is clearly acyclic. Furthermore, σ is a linear extension of P_{θ_{σ}} and we claim that a map τ : P_{θ_{σ}} → [p] is a linear extension of P_{θ_{σ}} if and only if τ ≅_{G} σ. In fact if τ is a linear extension of P_{θ_{σ}} and (u, v) ∈ E is such that σ(u) < σ(v) then u ⪯ v in P_{θ_{σ}} and hence τ(u) < τ(v) (since τ is a linear extension). Conversely if τ ≅_{G} σ and u ⪯ v in P_{θ_{σ}} then there exists a directed path u = v_{0} → v_{1} → … → v_{t} = v in θ_{σ}. This implies that σ(u) = σ(v_{0}) < σ(v_{1}) < … < σ(v_{t}) = σ(v) and hence (since (v_{i}, v_{i+1}) ∈ E for i = 0, …, t − 1, and σ ≅_{G} τ) that τ(u) = τ(v_{0}) < τ(v_{1}) < … < τ(v_{t}) = τ(v). Hence τ is a linear extension of P_{θ_{σ}}, as claimed. Therefore

∑_{τ:P_{θσ} →[p]} x^{a(σ(τ^{−1}(1)),...,σ(τ^{−1}(p)))+1} = ∑_{τ∈S_{p}(σ)} x^{a(σ∘τ^{−1})+1} ,  (25)

the sum on the left being over all linear extensions τ of P_{θ_{σ}}. Now, it is clear that, given σ_{1}, σ_{2} ∈ S_{p}, θ_{σ_{1}} = θ_{σ_{2}} if and only if σ_{1} ≅_{G} σ_{2}. Therefore the polynomial on the RHS of (25) actually depends only on S_{p}(σ). Furthermore, it is easy to see that for any acyclic orientation θ ∈ A(G) there is at least a σ ∈ S_{p} such that θ = θ_{σ}. Hence

∑_{θ∈A(G)} ∑_{τ :P_{θ}→[p]} x^{a(w(τ^{−1}(1)),...,w(τ^{−1}(p)))+1} = ∑_{i=1}^{a(G)} ∑_{τ∈S_{p}(σ_{i})} x^{a(σ_{i}∘τ^{−1})+1} ,  (26)

where σ_{1}, …, σ_{a(G)} are a complete set of distinct representatives of S_{p} modulo ≅_{G} and the polynomial on the LHS of (26) is the same polynomial as in the RHS of (20). Thus, comparing (20) and (26) yields the desired result. □

By the definition of the w-polynomial the preceding result yields the following new expansion of the chromatic polynomial of a graph. Theorem 4.4: Let G be a graph on p vertices. Then

χ(G; x) = ∑_{i=1}^{a(G)} ∑_{τ∈S_{p}(σ_{i})} (\begin{matrix}x+p−a(σ_{i}∘τ^{−1})−1 \\ p \end{matrix}) ,  (27)

where S_{p}(σ) and σ_{1}, … σ_{a(G)} have the same meaning as in Theorem 4.3. □

We illustrate Theorems 4.3 and 4.4 with an example. Let G = (V, E) be the path on 3 vertices, and assume that V = [3], and E = {(1, 2), (2, 3)}. Then there are 4 equivalence classes of S_{3} modulo ≅_{G}, namely {123}, {132 , 231}, {312 , 213}, and {321}, where we are writing permutations in one-line notation, (i.e. a_{1} … a_{n} represents the map that sends i to a_{i}, for i = 1, …, n). Hence, letting σ_{1} = 123, σ_{2} = 132, σ_{3} = 312, and σ_{4} = 321, we have that by Theorem 4.3,

w(G; x) = ∑_{i=1}^{4} ∑_{τ∈S_{3}(σ_{i})} x^{a(σ_{i}∘τ^{−1})+1}
= ∑_{τ∈{123}} x^{a(123∘τ^{−1})+1} + ∑_{τ∈{132,231}} x^{a(132∘τ^{−1})+1} + ∑_{τ∈{312,213}} x^{a(312∘τ^{−1})+1}
+ ∑_{τ∈{321}} x^{a(321∘τ^{−1})+1}
= x^{a(123)+1} + (x^{a(123)+1} + x^{a(213)+1}) + (x^{a(123)+1} + x^{a(132)+1}) + x^{a(123)+1}
= 4x^{3} + 2x^{2} ,

and hence, by the definition (18) of the w-polynomial,

χ(G; x) = 2 (\begin{matrix}x+1 \\ 3 \end{matrix}) + 4 (\begin{matrix}x \\ 3 \end{matrix}) .

As a consequence of Theorem 4.3 we obtain the following result. Proposition 4.5: Let G be a graph on p vertices and (18) be its w-polynomial. Then ∑_{i=1}^{p} w_{i} = p!, w_{i} = 0 if 0 ≤ i ≤ ν(G) − 1, w_{i} ∈ P for i = ν(G), …, p and w_{p} equals the number of acyclic orientations of G. Proof: The first assertion follows by letting x = 1 in (24). To prove the second one let σ, τ ∈ S_{p} be G-equivalent, a_{1}, …, a_{r} ∈ [p − 1] be the ascents of

(σ(τ^{−1}(1)), …, σ(τ^{−1}(p))), and B_{k} =^{def} {a_{k} + 1, a_{k} + 2, …, a_{k+1}}, for k = 0, …, r

(where a_{0} =^{def} 0, a_{r+1} =^{def} p). Fix now 0 ≤ k ≤ r, then for all x, y ∈ B_{k}, we have that x < y ⇒ σ(τ^{−1}(x)) > σ(τ^{−1}(y)). But this implies that (τ^{−1}(x), τ^{−1}(y)) ∉ E (otherwise, since σ ≅_{G} σ, we would have that x < y ⇒ τ(τ^{−1}(x)) < τ(τ^{−1}(y)) ⇒ σ(τ^{−1}(x)) < τ(τ^{−1}(y)). Hence τ^{−1}(B_{k}) is an independent set of G, for k = 0, …, r. Since τ^{−1}(B_{0}), …, τ^{−1}(B_{r}) are a partition of V this implies that ν(G) ≤ r + 1 and hence that a(σ ∘ τ^{−1}) + 1 ≥ ν(G). Since this holds for all σ, τ ∈ S_{p} that are Gequivalent we conclude, from (24), that w_{i} = 0 if 0 ≤ i ≤ ν(G) − 1. To prove the third assertion let ν(G) ≤ r ≤ p and let V_{1}, …, V_{r} be a partition of V into exactly r independent sets. Choose a bijection σ : V → [p] with the property that

σ(V_{j+1}) = {i_{j} + 1, i_{j} + 2, …, i_{j+1}}

for j = 0, …, r − 1, (where i_{j} =^{def} ∑_{k=1}^{j} |V_{j}| for 1 ≤ j ≤ r, and i_{0} =^{def} 0), and define a bijection τ : V → [p] by letting

τ(σ^{−1}(i_{j} + k)) =^{def} i_{j+1} − k + 1

for j = 0, …, r − 1, 1 ≤ k ≤ |V_{j+1}|. It is then easy to see that σ ≅_{G} τ, and that, by our definitions, a(τ ∘ σ^{−1}) = r − 1. Since any system of distinct representatives of S_{p} modulo ≅_{G} may be used in (24) to compute w(G; x) we may assume that σ is an element of {σ_{1}, …, σ_{a(G)}} in (24). Since τ ∈ S_{p}(σ) and a(τ ∘ σ^{−1}) + 1 = r this implies that w_{r} > 0, as desired. Finally, for every fixed θ ∈ A(G) and linear extension w_{θ} of P_{θ}, the polynomial

∑_{σ:P_{θ}→[p]} x^{a(w_{θ}(σ^{−1}(1)),...,w_{θ}(σ^{−1}(p)))+1}

is monic of degree p (since a(w_{θ}(σ^{−1}(1)), …, w_{θ}(σ^{−1}(p))) = p − 1 if and only if σ = w_{θ}). Hence, taking the coefficients of x^{p} on both sides of (20) gives that w_{p} = |A(G)|, as desired. □

Note that the fact that x^{ν(G)} divides w(G; x) may also be easily established from (19) using the combinatorial definition of χ(G; n) for n ∈ N. However, we thought a direct, combinatorial proof, to be preferable, and we thank Andreas Blass for suggesting the combinatorial argument given in the proof of the preceding Proposition.

One of the main reasons for considering the w-polynomial of a graph is that it can be used to derive information about some of the polynomials already considered in this work. In fact, we have the following results. Theorem 4.6: Let G be a graph on p vertices. Then

w(G; x) = (1 − x)^{p} \overline{σ} (G; \frac{x}{1 − x}) .  (28)

In particular, w(G; x) has only real zeros if and only if \overline{σ}(G; x) does. Proof: Equation (28) is an easy consequence of the definitions (18) and (16) of w(G; x) and \overline{σ}(G; x), and of the binomial theorem (see also [9], Thm.2.3.3). The second assertion follows from (28). □ Theorem 4.7: Let G be a graph and suppose that w(G; x) is log-concave. Then both \overline{σ}(G; x) and σ(G; x) are log-concave. Proof: Let (18) and (16) be the w-polynomial and augmented σ-polynomial of G, respectively. Then, from (1) and (17) we conclude that

∑_{i=0}^{p} w_{i} (\begin{matrix}x+p−i \\ p \end{matrix}) = ∑_{i=0}^{p}(a_{i}) (i!) (\begin{matrix}x \\ i \end{matrix}) .  (29)

Since, by hypothesis, the sequence {w_{0}, …, w_{p}} is log-concave, and by Proposition 4.5 it has no internal zeros, there follows from (29), and Prop.2.5.1 and Thm. 2.5.8 of [9] that the sequence {a_{0}, a_{1}, a_{2}(2!), …, a_{p}(p!)} is also log-concave. This shows that \overline{σ}(G; x) is log-concave and this implies, by Proposition 3.24, that σ(G; x) is also log-concave. □

As an immediate consequence of Theorems 4.6 and 3.22 we obtain the following result. Theorem 4.8: Let G be a graph and suppose that w(G; x) has only real zeros. Then σ(G; x) has only real zeros. □

We now come to one of the main results of this section. Theorem 4.9: Let G be a graph such that χ(G; x) has all its zeros in the half open interval [0, ν(G)). Then w(G; x) has only real zeros. Proof: By hypothesis λ(χ(G; x)) ≥ 0 and Λ(χ(G; x)) < ν(G). Also, it is clear from the combinatorial interpretation of the chromatic polynomial that χ(G; x) = 0 for all x ∈ [0, ν(G)) ∩ Z. Hence, by Theorem 2.2 and the definition (18) of the w-polynomial we have that w(G; x) has only real zeros, as desired. □

We now present a general class of graphs whose w-polynomials always have only real zeros. A graph G on p vertices is called supersolvable if there is an indexing v_{1}, …, v_{p} of the vertices of G such that if 1 ≤ i < j < k ≤ p and v_{k} is adjacent to v_{i} and v_{j}, then v_{i} and v_{j} are adjacent. In other words, the vertices adjacent to v_{k} among v_{1}, …, v_{k−1} induce a complete subgraph of G, for k = 1, …, p. This concept was first introduced and studied by Stanley in the more general setting of lattices (see [43]). Intuitively, we may think of a supersolvable graph as one which can be reduced to K_{1} by taking away one vertex at a time so that, each time, we are only allowed to take away a vertex whose neighborhood is a clique. So, for example, the graphs T (t, m, n) (defined in §3) are supersolvable, while the graphs V (t, m, n) are not, except if t = 1.

Our interest in supersolvable graphs stems from the fact that their chromatic polynomials have a nice closed form, as the next result shows. Theorem 4.10: Let G = (V, E) be a supersolvable graph on p vertices. Then there exist nonnegative integers a_{1}, …, a_{p} such that

χ(G; x) = ∏_{i=1}^{p}(x − a_{i}) .  (30)

Proof: Let G be a supersolvable graph and let v_{1}, …, v_{p−1}, v_{p} be an indexing of the vertices of G as in the definition. For i = 1, …, p, let a_{i} =^{def} |{j < i : (v_{j}, v_{i}) ∈ E}|, (so that a_{1} = 0). Then we can color G in x colors by first coloring v_{1} in x ways, then v_{2} in x − a_{2} ways, etc..., and (30) follows. □

The previous theorem is a special case of Thm. 4.1 of [43] about supersolvable lattices, however, we thought a direct, self-contained proof, to be more illuminating. Theorems 4.9 and 4.10 immediately imply one of the main results of this section. Theorem 4.11: Let G be a supersolvable graph. Then w(G; x) has only real zeros. □

As an immediate Corollary of Theorems 4.8 and 4.11 we obtain the following result which was first proved, though stated in a slightly different language, in [55], Thm. 3.5. Corollary 4.12: Let G be a supersolvable graph. Then σ(G; x) has only real zeros. □

Other immediate consequences of Theorem 4.11 are the following, which, by Theorem 4.8, strengthen Corollaries 3.6, and 3.21, respectively. Corollary 4.13: Let N_{p} be the empty graph on p vertices. Then w(N_{p}; x) has only real zeros.□ Corollary 4.14: Let G be a tree. Then w(G; x) has only real zeros. □

The reader should note that it follows easily from Theorem 4.3 that

w(N_{p}; x) = ∑_{τ∈S_{p}} x^{a(τ)+1} .  (31)

The polynomial on the RHS of (31) is called the p-th Eulerian polynomial and has been widely studied (see, e.g, [48], p.22, for further information about Eulerian polynomials). Thus, Corollary 4.13 is equivalent to the well known (see, e.g., [14], p.292, Ex.3), but non-trivial fact, that the Eulerian polynomials have only real zeros. Hence Theorem 4.11 is a generalization of this well known result. Note that there are graphs whose chromatic polynomial do not have only real zeros but that satisfy the hypotheses of Theorem 3.3 (take, e.g., C_{4}). Therefore Theorem 3.3 is not a special case of Theorem 4.9.

There is an elegant characterization of supersolvable graphs (mentioned in [43], p.205) which is sometimes more convenient to handle than the original definition. Recall (see, e.g., [19], p.48) that a graph G is chordal (sometimes also called triangulated) if every cycle of G has a chord. Theorem 4.15: Let G be a graph. Then G is supersolvable if and only if G is chordal. □

It is easy to see that if G is supersolvable then G is chordal. The converse, however, is not obvious, and we refer the reader to [16], [19], or [39], for a proof.

We now prove that the operation introduced in the paragraph preceding Theorem 3.20 also preserves the property of the w-polynomial having only real zeros. In order to do this, we need the following analytical result, which is an immediate consequence of Thm. 4.4.3 of [9]. Theorem 4.16: Let G and H be two graphs. Suppose that w(G; x) has only real zeros and that

χ(H; x) = (x − c) χ(G; x) ,  (32)

where 0 ≤ c ≤ ν(G). Then w(H; x) has only real zeros. □

The following result is the analogue of Theorem 3.20 for w-polynomials. Its proof is similar to that of Theorem 3.20 and is omitted. Theorem 4.17: Let G = (V, E) be a graph such that w(G; x) has only real zeros. Then w(G_{v,n}; x) has only real zeros for all v ∈ V and n ∈ N. □

We conclude this section with a result that is a consequence of Theorem 2.3 and the obvious fact that χ(G ⊎ H; x) = χ(G; x) χ(H; x). It is the analogue, for w-polynomials, of Theorem 3.12. Theorem 4.18: Let G and H be two graphs. Suppose that w(G; x) and w(H; x) have only real zeros. Then w(G ⊎ H; x) has only real zeros. □

5 The τ-polynomial

Let G be a graph on p vertices and let

χ(G; x) = ∑_{i=0}^{p}(−1)^{p−i} c_{i}⟨x⟩_{i} ,  (33)

(where ⟨x⟩_{i} =^{def} x(x + 1) … (x + i − 1), for i ≥ 1, and ⟨x⟩_{0} =^{def} 1), be its chromatic polynomial. The τ-polynomial of G is the polynomial defined by

τ(G; x) =^{def} ∑_{i=0}^{p} c_{i} x^{i} .  (34)

The τ-polynomial of a graph is, in some sense, a “dual” of the σ-polynomial. The next two results give some of its basic properties. Proposition 5.1 (Decomposition): Let G be a graph and let u and v be two adjacent vertices of G. Then

τ(G; x) = τ(G′; x) + τ(G′′; x) ,

where G′ (respectively, G′′) is the graph obtained from G by removing the edge between u and v (respectively, identifying u and v). Proof: It is well known (see, e.g., [36], Thm.1, or [3], Prop.9.3) and easy to see that

χ(G′; x) = χ(G; x) + χ(G′′; x) .  (35)

The thesis then follows from (35), (33), and (34). □

We now proceed to give a combinatorial interpretation of the coefficients of τ(G; x). To do this, we need the following result. (Recall that, given a graph G, we denote by a(G) the number of acyclic orientations of G.) Lemma 5.2: Let G be a graph and let u and v be two adjacent vertices of G. Then

a(G) = a(G′) + a(G′′) .

where G′ and G′′ have the same meaning as in Proposition 5.1. Proof: Letting x = n in (35) yields that

χ(G′; n) = χ(G; n) + χ(G′′; n)

multiplying both sides of this equation by x^{n} and summing over all n ∈ N gives, by (19), that

w(G′; x) = w(G; x) + (1 − x) w(G′′; x) .  (36)

But, by Proposition 4.5, the leading coefficient of w(H; x) equals a(H), for any graph H. Hence taking the coefficients of x^{p} on both sides of (36) establishes the Lemma. □

Using the preceding Lemma we can give a combinatorial interpretation of the coefficients of τ(G; x). Let V be a finite set, we denote by Π(V) the set of all partitions of V. Given a function f : V → [n] (n ∈ P) we let π_{f} be the partition of V defined by letting i, j ∈ V be in the same block of π_{f} if and only if f(i) = f(j). We call π_{f} the partition of V induced by f. Given π, σ ∈ Π(V) we let π ⪯ σ if and only if every block of π is contained in a block of σ. This makes Π(V) into a partially ordered set (actually, into a geometric lattice) and we refer the reader to [48] or [51] for further information about it. Given u, v ∈ V we will denote by uv the partition of V having all blocks of cardinality 1 except for the block {u, v}. For π ∈ Π(V) we denote by |π| the number of blocks of π. Let now G = (V, E) be a graph. Given a subset B ⊆ V we denote by G(B) the subgraph of G induced by B (i.e., G(B) =^{def} (B, E(B)), where E(B) =^{def} {(u, v) ∈ E : u, v ∈ B}). Given a partition π of V we let G(π) =^{def} ⨄_{B∈π} G(B). We can now prove one of the main results of this section. Theorem 5.3: Let G = (V, E) be a graph on p vertices and q edges and τ(G; x) be its τ-polynomial. Then

τ(G; x) = ∑_{π∈Π(V)} a(G(π)) x^{|π|} .  (37)

Proof: We prove the result by induction on p + q. The result is easily verified for p + q ≤ 2. So assume that (37) holds for all graphs G = (V, E) such that |V | + |E| ≤ p + q − 1 and let G be a graph on p vertices and q edges. If q = 0 then G = N_{p} and hence χ(G; x) = x^{p}. But it is well known (see, e.g., [48], p.209) that x^{p} = ∑_{i=0}^{p}(−1)^{p−i} S(p, i) ⟨x⟩_{i}, so from (33) and (34) we conclude that τ(N_{p}; x) = ∑_{i=0}^{p} S(p, i) x^{i}. But if G = N_{p} then G(π) = N_{p} for all π ∈ Π(V). Therefore ∑_{π∈Π(V)} a(G(π)) x^{|π|} = ∑_{π∈Π(V)} x^{|π|} = ∑_{i=0}^{p} S(p, i) x^{i}, as desired. So suppose that there are u, v ∈ V such that (u, v) ∈ E, and let G′ and G′′ have the same meaning as in Proposition 5.1. Note that we have a natural bijection

φ : {π ∈ Π(V) : uv ⪯ π} → Π(V \ {u})

and that G(π)′ = G′(π) and G(π)′′ = G′′(φ(π)) if π ⪰ uv. Also note that if π ≱ uv then G(π) = G′(π). Then we have that

∑_{{π∈Π(V): π⪰uv}} a(G(π))x^{|π|} = ∑_{{π∈Π(V): π⪰uv}}(a(G(π)′) + a(G(π)′′)) x^{|π|}

= ∑_{{π∈Π(V): π⪰uv}}(a(G′(π)) + a(G′′(φ(π)))) x^{|π|}

= ∑_{{π∈Π(V): π⪰uv}} x^{|π|}a(G′(π)) + ∑_{π∈Π(V \{u})} x^{|π|}a(G′′(π))

Hence

∑_{π∈Π(V)} x^{|π|} a(G(π)) = ∑_{{π∈Π(V): π⪰uv}} x^{|π|}a(G(π)) + ∑_{{π∈Π(V): π⪰̸uv}} x^{|π|} a(G′(π))
= ∑_{π∈Π(V \{u})} x^{|π|} a(G′′(π)) + ∑_{π∈Π(V)} x^{|π|} a(G′(π))
= τ(G′′; x) + τ(G′; x)
= τ(G; x)

by Proposition 5.1 and our induction hypotheses. This proves (37) for G and concludes the induction step and hence the proof. □

As an immediate consequence of the preceding theorem we obtain the following result. Corollary 5.4: Let G be a graph on p vertices and q edges and (34) be its τpolynomial. Then, for i = 0, …, p, we have that

c_{i} = ∑_{{π∈Π(V):|π|=i}} a(G(π)) .

In particular, c_{0} = 0, c_{1} = a(G), c_{i} ≥ 1 for i = 2, …, p − 2, c_{p−1} = \binom{p}{2} + q, and c_{p} = 1. □

By the definition of the τ-polynomial Theorem 5.3 yields the following new expansion of the chromatic polynomial of a graph. Theorem 5.5: Let G = (V, E) be a graph on p vertices. Then

χ(G; x) = ∑_{π∈Π(V)} a(G(π)) (−1)^{p−|π|} ⟨x⟩_{|π|} .□

We illustrate Theorems 5.3 and 5.5 with an example. Let G = (V, E) be the cycle on 3 vertices and assume that V = [3], and E = {(1, 2), (2, 3), (3, 1)}. Then there are 5 partitions of V, namely, π_{1} = {1, 2, 3}, π_{2} = {1} ∪ {2, 3}, π_{3} = {2} ∪ {1, 3}, π_{4} = {3} ∪ {1, 2}, and π_{5} = {1} ∪ {2} ∪ {3}. Hence,

τ(G; x) = a(G({1, 2, 3})) x^{1} + a(G({1} ∪ {2, 3})) x^{2}
+ a(G({2} ∪ {1, 3})) x^{2} + a(G({3} ∪ {1, 2})) x^{2}
+ a(G({1} ∪ {2} ∪ {3})) x^{3}
= 6x + 6x^{2} + x^{3} ,

and therefore

χ(G; x) = 6⟨x⟩_{1} − 6⟨x⟩_{2} + ⟨x⟩_{3} .

We now introduce a modified version of the τ-polynomial that will serve the same purpose as \overline{σ}(G; x) does for σ(G; x). Let G be a graph on p vertices and let (34) be its τ-polynomial. Then the augmented τ-polynomial of G is the polynomial defined by

\overline{τ}(G; x) =^{def} ∑_{i=0}^{p}(i!) c_{i} x^{i} .  (38)

As another immediate consequence of Theorem 5.3 we obtain the following combinatorial interpretation of the coefficients of \overline{τ}(G; x). Theorem 5.6: Let G be a graph on p vertices and let (38) be its augmented τpolynomial. Then, for i = 0, …, p, we have that

(i!) c_{i} = ∑_{{σ:V →[i] \atop σ onto}} a(G(π_{σ})) ,

where π_{σ} is the partition of V induced by σ. □

As a consequence of Theorem 5.6 we obtain the following combinatorial interpretation of the chromatic polynomial of a graph evaluated at negative integers. Theorem 5.7: Let G be a graph on p vertices. Then, for n ∈ P, we have that

(−1)^{p} χ(G; −n) = ∑_{σ:V →[n]} a(G(π_{σ})) .  (39)

Proof: Fix n ∈ P. Letting x = −n in (33) we obtain that

(−1)^{p} χ(G; −n) = ∑_{i=1}^{p}(i!) c_{i} \binom{n}{i}

and the thesis follows from Theorem 5.6. □

Let θ ∈ A(G) and n ∈ P, a map σ : V → [n] is said to be θ-compatible if u → v implies σ(u) ≥ σ(v). We can now prove the following result originally due to R. Stanley (see [44], Thm.1.2), and frequently rediscovered in the case n = 1, (see, e.g., [60], p.202). Theorem 5.8: Let G be a graph on p vertices. Then, for n ∈ P, (−1)^{p} χ(G; −n) equals the number of pairs (θ, σ) where θ is an acyclic orientation of G and σ : V → [n] is a θ-compatible map. In particular, (−1)^{p} χ(G; −1) equals the number of acyclic orientations of G. Proof: It is not hard to see that, for each map σ : V → [n], there are exactly a(G(π_{σ})) acyclic orientations θ of G such that σ is θ-compatible. The thesis hence follows from (39). □

The main connections between the zeros and log-concavity properties of w(G; x) and \overline{τ}(G; x) are given in the next two results. We omit the proof of the first one since it is similar to that of Theorem 4.6. Theorem 5.9: Let G be a graph on p vertices. Then

w(G; x) = (x − 1)^{p} x \overline{τ} (G; \frac{1}{x − 1}) .  (40)

In particular, w(G; x) has only real zeros if and only if \overline{τ}(G; x) does. □ Theorem 5.10: Let G be a graph and suppose that w(G; x) is log-concave. Then both \overline{τ}(G; x) and τ(G; x) are log-concave. Proof: Let (18) and (38) be the w-polynomial and augmented τ-polynomial of G, respectively. Then, by (17) and (33), we have that

∑_{i=1}^{p} w_{i} (\begin{matrix}x+p−i \\ p \end{matrix}) = ∑_{i=1}^{p}(−1)^{p−i} c_{i} ⟨x⟩_{i} .  (41)

Letting now x = −x in (41) and then multiplying both sides by (−1)^{p} yields

∑_{i=1}^{p} w_{p−i+1} (\begin{matrix}x+p−i \\ p \end{matrix}) = ∑_{i=1}^{p} c_{i} (i!) (\begin{matrix}x \\ i \end{matrix}) .  (42)

By our hypotheses and Proposition 4.5 the sequence {w_{p}, …, w_{2}, w_{1}} is log-concave with no internal zeros, hence by (42), and Prop.2.5.1 and Thm.2.5.8 of [9], the sequence \{c_{0}, c_{1}, c_{2}(2!), …, c_{p}(p!)\} is log-concave. This shows that \overline{τ}(G; x) is logconcave. The second statement follows easily from the first one. □

Note that the preceding result is the analogue, for τ(G; x) and \overline{τ}(G; x), of Theorem 4.7. We conclude this section with a curious consequence of Theorem 5.9. Proposition 5.11: Let G be a graph. Then

\overline{τ}(G; 1) = \frac{1}{2} w(G; 2) .□  (43)

It would be interesting to have a combinatorial proof of (43) based on Theorems 4.3 and 5.3. Note that, by Theorem 4.6, Theorem 5.9 also implies that, for a graph G, \overline{σ}(G; x) has only real zeros if and only if \overline{τ}(G; x) does. Also, since the relationship between τ(G; x) and \overline{τ}(G; x) is identical to the one between σ(G; x) and \overline{σ}(G; x) Theorems 3.22 and 3.23 and Proposition 3.24 still hold when “σ” is replaced by “τ” throughout their statements. Finally, by Theorem 5.9, all the results obtained in the preceding section about the zeros of w(G; x) (namely Theorems 4.9, 4.11, 4.16, 4.17, and 4.18 and Corollaries 4.13 and 4.14) also hold for \overline{τ}(G; x).

6 Chromatic polynomials

In this section we study the zeros and log-concavity properties of the chromatic polynomial itself and the connections between these and those of the polynomials studied in the preceding sections. Our first result is the following. Theorem 6.1: Let G be a graph. Suppose that χ(G; x) has only real zeros, then τ(G; x) has only simple real zeros. Proof: Let (34) be the τ-polynomial of G. Since χ(G; x) has only real (necessarily nonnegative) zeros, there follows from (33) that the polynomial ∑_{i=1}^{p} c_{i} (x)_{i} has only real nonpositive zeros. But by Thm. 2.4.2 of [9] this implies that ∑_{i=1}^{p} c_{i} x^{i} has only simple real zeros, as desired. □

Note that the converse of Theorem 6.1 does not hold (take, e.g., G = C_{4}). We investigate next the log-concavity properties of the coefficients of χ(G; x). (We refer the reader to [3], p. 88, for the definition of the internal and external activities of a spanning tree.) Theorem 6.2: Let G be a connected graph on p vertices and let, for i = 1, …, p−1, t_{i} be the number of spanning trees of G having internal activity i and external activity 0. Suppose that the sequence {t_{1}, …, t_{p−1}} is log-concave with no internal zeros, then (−1)^{p}χ(G; −x) is log-concave.

Proof: It follows from our definitions and Theorem 1.4.1 on p.94, of [3] that

(−1)^{p} χ(G; −x) = x ∑_{i≥0} t_{i} (1 + x)^{i}
= ∑_{j≥0} (∑_{i≥0} t_{i} (\begin{matrix}i \\ j \end{matrix} )) x^{j+1} ,  (44)

(where t_{i} =^{def} 0 if i ≥ p or i = 0). But, by our hypotheses, the sequence {t_{i}}_{i∈N} is log-concave with no internal zeros (and eventually vanishing), hence, by Prop. 2.5.1 and Thm. 2.5.3 of [9], the sequence

\{∑_{i≥0} t_{i} (\begin{matrix}i \\ j \end{matrix} )\}_{j∈N}

is log-concave and the thesis follows from (44). □

We now consider the log-concavity of the sequence {χ(G; n)}_{n=0,1,2,...}. Our main result in this direction is the following. Theorem 6.3: Let G be a graph and suppose that \overline{σ}(G; x) is log-concave. Then the sequence {χ(G; n)}_{n=0,1,2,...} is log-concave. Proof: Let (16) be the augmented σ-polynomial of G. By our hypotheses, the sequence {a_{0}, 1a_{1}, 2!a_{2}, …, p!a_{p}} is log-concave, and, by Theorem 3.1, it has no internal zeros. Therefore, by (1) and Theorem 2.5.7 of [9], the sequence {χ(G; n)}_{n=0,1,2,...} is log-concave, as desired. □

Note that, by the preceding result and Theorems 3.23 and 4.8, all the results obtained in §3 and §4 about the reality of the zeros of w(G; x) and σ(G; x) give rise to a number of classes of graphs for which the sequence {χ(G; n)}_{n∈N} is log-concave.

7 Conjectures and Open Problems

There are several problems that are suggested by the research presented in this work. The main one is probably the following. Problem 7.1: Does the polynomial τ(G; x) have only real zeros for all graphs G?

We have verified that the answer is yes for all connected graphs on ≤ 8 vertices. G. F. Royle (private communication) has recently found that σ(G; x) does not always have only real zeros. However, we do feel that the following statements are true. (We refer the reader to [3], p. 63, for the definition of prisms and Möbius ladders.)

Conjecture 7.2: Let G be a graph on p vertices and suppose that ν(G) ≥ p − 3. Then σ(G; x) has only real zeros. Conjecture 7.3:Let G = (V, E) be a prism, a cycle or a Möbius ladder. Then σ(G; x) has only real zeros.

If ν(G) ≥ p − 2 then Conjecture 7.2 holds by Theorem 3.8. The chromatic polynomials of connected graphs G on p vertices such that ν(G) = p − 3 have been completely classified by Dhurandhar in [15] and Conjecture 7.2 might follow from this characterization. We should warn the reader, however, that some printing errors are present in [15]. Besides the wrong formula on p. 220 for a_{p−2} (see Proposition 3.2 of the present work for the correct formula) the constant term of σ(G_{4}) on p. 218 of [15] should be “5r −28” instead of “5r −23” and the coefficient of σ in σ(G_{12}) on p. 219 should be 17 instead of 19. We don’t know if other printing errors are present in [15]. Conjecture 7.3 has been verified for |V | ≤ 14.

The graph in Figure 3 at the end of §3 and Theorems 4.6 and 5.9 shows that w(G; x), \overline{τ}(G; x), and \overline{σ}(G; x) do not always have only real zeros. However, it would be interesting to know for which graphs G this is true. The graph G = C_{5} shows that the condition of χ(G; x) having all its zeros in [0, ν(G)) (though sufficient, by Theorem 4.9) is not necessary for w(G; x) to have only real zeros. The main open problem about w(G; x), \overline{τ}(G; x), and \overline{σ}(G; x), however, is the following. Problem 7.4: Are the polynomials w(G; x), \overline{τ}(G; x), and \overline{σ}(G; x) log-concave (or just unimodal) for every graph G?

We have verified that the answer to the above questions is yes for connected graphs on ≤ 7 vertices. Note that, by Theorems 4.7 and 5.10, if w(G; x) is logconcave then both \overline{σ}(G; x) and \overline{τ}(G; x) are also log-concave. Also, by Theorem 3.23, if the answer to Problem 7.1 is yes for σ(G; x) (respectively, τ(G; x)) then the answer to Problem 7.4 is also yes for \overline{σ}(G; x) (respectively \overline{τ}(G; x)).

Regarding the chromatic polynomial itself we feel that the following statement holds. Conjecture 7.5: Let G be a graph. Then the sequence {χ(G; n)}_{n∈N} is log-concave.

If the answer to Problem 7.1 is affirmative for σ(G; x) then, by Theorems 3.23 and 6.3, Conjecture 7.5 would follow. Also, if the answer to Problem 7.4 is yes for \overline{σ}(G; x) (or if w(G; x) is log-concave) then, by Theorems 4.7 and 6.3, Conjecture 7.5 would again follow. In particular, Conjecture 7.5 holds for all graphs on ≤ 7 vertices.

Finally, let us mention the following conjecture, due to Read for unimodality (see [36], p.68) and to Welsh (in the more general setting of matroids, see [57], Ex.5, p.

266) for log-concavity. Conjecture 7.6: Let G be a graph, then the polynomial (−1)^{p}χ(G; −x) is logconcave (and hence, in particular, unimodal).

Because this conjecture has already received a considerable amount of interest we don’t dwell on it here but instead refer the reader to [20] for more information about it. However, one of the aims of this work has been to show that Conjecture 7.6 is only one of a whole class of similar problems that are all interconnected and worth investigating. Acknowledgements. The author would like to thank Andreas Blass, Phil Hanlon, John Stembridge, and David Wagner for many valuable suggestions and comments, E. G. Whitehead, Jr, for kindly providing extensive tables of chromatic polynomials, and the referee for suggesting a simplification in the proof of Theorem 5.3.

References

[1] R. A. Bari, Regular Major Maps of at Most 19 Regions and Their Q-Chromials, J. Combin. Theory Ser. B 12 (1972), 132-142.

[2] E. Bertin and R. Theodorescu, On the unimodality of Discrete Probability Measures, Math. Zeitschrift, 201 (1989), 131-137.

[3] N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974.

[4] G. D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. of Math. (2) 14 (1912-13), 43-46.

[5] G. D. Birkhoff, On the polynomial expressions for the number of ways of coloring a map, Ann. Scuola Norm. Sup. (Pisa) (2) 3 (1934), 85-104.

[6] G. D. Birkhoff and D. C. Lewis, Chromatic Polynomials, Trans. Amer. Math. Soc. 60 (1946), 355-451.

[7] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, New York-Amsterdam-Oxford, 1976.

[8] F. Brenti, Unimodal, Log-concave and Polya Frequency Sequences in Combinatorics, Ph.D. Thesis, June 1988, Massachusetts Institute of Technology.

[9] F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no.413, 1989.

[10] F. Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc., 108 (1990), 1133-1141.

[11] F. Brenti, Log-concavity and combinatorial properties of Fibonacci Lattices, preprint.

[12] F. Brenti, Unimodality, excedances, and symmetric functions, preprint.

[13] L. Butler, A unimodality result in the enumeration of subgroups of a finite abelian group, Proc. Amer. Math. Soc., 101(1987),771-775.

[14] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.

[15] M. Dhurandhar, Characterization of Quadratic and Cubic σ-polynomials, J. Combin. Theory Ser. B 37 (1984) 210-220.

[16] G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71-76.

[17] D. C. Foata and M. P. Schützenberger, On the rook polynomials of Ferrers relations, Colloq. Math. Soc. Janos Bolyai, 4, Combinatorial Theory and its Applications, vol. 2 (P. Erdös et al., eds.), North-Holland, Amsterdam, 1970.

[18] R. W. Frucht and R. E. Giudici, Some chromatically unique graphs with seven points, Ars Combin. 16-A (1983) 161-172.

[19] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B 16, (1974) 47-56.

[20] D. Gernert, A survey of partial proofs for Read’s conjecture and some recent results, IX symposium on operations research. Part I. Sections 1-4 (Osnabruck, 1984), 233-238, Methods Oper. Res., 49, Athenaum/Hain/Hanstein, Konigstein/Ts., 1985.

[21] P. Gilmore and A. J. Hoffman, A characterization of comparability graphs and interval graphs, Canad. J. Math. 16 (1964), 539-548.

[22] R. E. Giudici and R. M. Vinke, A table of chromatic polynomials, J. Combin. Inform. System Sci., 5 (1980), 323-350.

[23] J. R. Goldman, J. T. Joichi, and D. E. White, Rook Theory. I. Rook equivalence of Ferrers Boards, Proc. Amer. Math. Soc. 52 (1975) 485-492.

[24] J. R. Goldman, J. T. Joichi, and D. E. White, Rook Theory III. Rook polynomials and the chromatic structure of graphs, J. Combin. Theory Ser. B 25 (1978) 135-142.

[25] F. Harary, Graph Theory, Addison Wesley, 1969.

[26] G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, 2nd ed., Cambridge Univ. Press, Cambridge, 1952.

[27] A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), 1-82.

[28] S. Karlin, Total Positivity, vol.1, Stanford University Press, 1968.

[29] R. R. Korfhage, σ-polynomials and graph coloring, J. Combin. Theory Ser. B 24 (1978) 137-153.

[30] R. R. Khorfage, A note on quadratic σ-polynomials, Discrete Math. 69 (1988) 195-196.

[31] A. Nijenhuis, On permanents and the zeros of rook polynomials, J. Combin. Theory Ser. A 21 (1976) 240-244.

[32] K. O’Hara, Unimodality of Gaussian coefficients: a constructive proof, J. Combin. Theory Ser. A. 53 (1990) 29-52.

[33] G. Pólya and G. Szegö, Problems and Theorems in Analysis, vols. I and II, Springer-Verlag, Berlin, Heidelberg, 1976.

[34] R. Proctor, Representations of sl(2,C) on posets and the Sperner property, SIAM J. Algebraic Discrete Methods 3 (1982), 275-280.

[35] R. Proctor, Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly, 89 (1982), 721-734.

[36] R. C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52-71.

[37] R. C. Read, A large family of chromatic polynomials, Proceedings of the Third Caribbean Conference on Combinatorics and Computing, (C. C. Cadogan Ed.), University of the West Indies Press, Barbados, 1981, 23-41.

[38] R. C. Read, Some Applications of Computers in Graph Theory, Selected Topics in Graph Theory, (L. W. Beineke and R. J. Wilson Eds.), Academic Press, London, 1978, 417-444.

[39] D. J. Rose, Triangulated Graphs and the Elimination Process, J. Math. Anal. Appl. 32 (1970) 597-609.

[40] B. Sagan, Inductive and injective proofs of log concavity results, Discrete Math., 68 (1988), 281-292.

[41] B. Sagan, Log-concave sequences of symmetric functions and analogs of the Jacobi-Trudi Determinant, preprint.

[42] R. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math. Soc., no.119, 1972.

[43] R. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197-217.

[44] R. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171-178.

[45] R. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), 139-157.

[46] R. Stanley, Unimodal sequences arising from Lie algebras, in Young Day Proceedings T. V. Narayana, R. M. Mathsen, and J. G. Williams, eds., Dekker, New York/Basel, 1980, pp. 127-136.

[47] R. Stanley, Unimodality and Lie superalgebras, Studies in Applied Math. 72 (1985), 263-281.

[48] R. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[49] R. Stanley, Generalized h-vectors, intersection cohomology of toric varieties, and related results, Advanced Studies in Pure Math. 11 (1987), 187-213.

[50] R. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics, and Geometry, Annals of the New York Academy of Sciences, 576 (1989), 500-534.

[51] D. Stanton and D. White, Constructive Combinatorics, Springer-Verlag, New York-Berlin-Heidelberg-Tokyo, 1986.

[52] W. T. Tutte, The Golden Ratio in the Theory of Chromatic Polynomials, Annals of the New York Academy of Sciences, Vol. 175, Art. 1, 391-402.

[53] W. T. Tutte, Chromials, Hypergraph Seminar, (C. Berge and D. Ray-Chaudhuri Eds.), Lecture Notes in Mathematics, no.411, Springer-Verlag, Berlin-Heidelberg-New York, 1974, 243-266.

[54] D. Wagner, Enumerative Combinatorics of partially ordered sets, and total positivity of Hadamard products, Ph.D. Thesis, 1989, Massachusetts Institute of Technology.

[55] D. Wagner, The partition polynomial of a finite set system, to appear in J. Combin. Theory Ser. A.

[56] D. Wagner, Total positivity of Hadamard products, preprint.

[57] D. Welsh, Matroid Theory, Academic Press, London/New York, 1976.

[58] D. E. White, Monotonicity and unimodality of the pattern inventory, Advances in Math. 38 (1980), 101-108.

[59] H. Whitney, The coloring of graphs, Ann. of Math. (2) 33 (1932), 688-718.

[60] D. R. Woodall, Zeros of Chromatic Polynomials, Proceedings of the Sixth British Combinatorial Conference, (P. J. Cameron, Ed.), Academic Press, 1977, 199-223.

[61] S.-J. Xu, On σ-polynomials, Discrete Math. 69 (1988) 189-194.

[62] D. Zeilberger, Kathy O’ Hara’ s Constructive Proof of the Unimodality of the Gaussian Polynomials, Amer. Math. Monthly, 96 (1989), 590-602.