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 1 r ! | χ G r ( 0 ) | , where χ G r is the rth derivative of χ G ( λ ) . We also define a complex Δ ( G ) C , whose r-faces consist of all ordered set partitions [ B 1 , … , B r + 2 ] where none of the B i contain an edge of G and where 1 ∈ B 1 . 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 [ x 1 , … , x n ] / { x i x j | i j 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.