(1) Department of Mathematics, Indiana University, Rawles Hall, Bloomington, IN 47405, USA;(2) Department of Mathematics, Cornell University, Ithaca, NY 14853, USA
Abstract:
Steingrimsson’s coloring complex and Jonsson’s unipolar complex are interpreted in terms of hyperplane arrangements. This
viewpoint leads to short proofs that all coloring complexes and a large class of unipolar complexes have convex ear decompositions.
These convex ear decompositions impose strong new restrictions on the chromatic polynomials of all finite graphs. Similar
results are obtained for characteristic polynomials of submatroids of type ℬn arrangements.
The first author was supported by NSF grant DMS-0500638. The second author was supported by NSF grant DMS-0245623.