The homology of the cyclic coloring complex of simple graphs

Let 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 , where is the rth derivative of χG(λ). We also define a complex ΔC(G), whose r-faces consist of all ordered set partitions B₁,…,Br+2] where none of the Bi contain an edge of G and where 1∈B₁. 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 Cx₁,…,xn]/{xixj|ij is an edge of G}. We show that when G is a connected graph, the homology of ΔC(G) has nonzero homology only in dimension n−2, and the dimension of this homology group is . In this case, we provide a bijection between a set of homology representatives of ΔC(G) and the acyclic orientations of G with a unique source at v, a vertex of G.