The homology of the cyclic coloring complex of simple graphs

AbstractLet G be a simple graph on n vertices, and let χG(λ) denote the chromatic polynomial of G. In this paper, we define the cyclic coloring complex, Δ(G), and determine the dimensions of its homology groups for simple graphs. In particular, we show that if G has r connected components, the dimension of (n−3)rd homology group of Δ(G) is equal to (n−(r+1)) plus 1r!|χGr(0)|, where χGr is the rth derivative of χG(λ). We also define a complex Δ(G)C, whose r-faces consist of all ordered set partitions [B1,…,Br+2] where none of the Bi contain an edge of G and where 1∈B1. We compute the dimensions of the homology groups of this complex, and as a result, obtain the dimensions of the multilinear parts of the cyclic homology groups of C[x1,…,xn]/{xixj|ij is an edge of G}. We show that when G is a connected graph, the homology of Δ(G)C has nonzero homology only in dimension n−2, and the dimension of this homology group is |χG′(0)|. In this case, we provide a bijection between a set of homology representatives of Δ(G)C and the acyclic orientations of G with a unique source at v, a vertex of G