The Topology of the Coloring Complex
Jakob Jonsson
jakob
DOI: 10.1007/s10801-005-6914-0
Abstract
In a recent paper, E. Steingrímsson associated to each simple graph G a simplicial complex 
G, referred to as the coloring complex of G. Certain nonfaces of G correspond in a natural manner to proper colorings of G. Indeed, the h-vector is an affine transformation of the chromatic polynomial 
G of G, and the reduced Euler characteristic is, up to sign, equal to | G(-1)|-1. We show that G is constructible and hence Cohen-Macaulay. Moreover, we introduce two subcomplexes of the coloring complex, referred to as polar coloring complexes. The h-vectors of these complexes are again affine transformations of G, and their Euler characteristics coincide with 
G(0) and - G(1), respectively. We show for a large class of graphs-including all connected graphs-that polar coloring complexes are constructible. Finally, the coloring complex and its polar subcomplexes being Cohen-Macaulay allows for topological interpretations of certain positivity results about the chromatic polynomial due to N. Linial and I. M. Gessel.
G, referred to as the coloring complex of G. Certain nonfaces of G correspond in a natural manner to proper colorings of G. Indeed, the h-vector is an affine transformation of the chromatic polynomial G of G, and the reduced Euler characteristic is, up to sign, equal to | G(-1)|-1. We show that G is constructible and hence Cohen-Macaulay. Moreover, we introduce two subcomplexes of the coloring complex, referred to as polar coloring complexes. The h-vectors of these complexes are again affine transformations of G, and their Euler characteristics coincide with G(0) and - G(1), respectively. We show for a large class of graphs-including all connected graphs-that polar coloring complexes are constructible. Finally, the coloring complex and its polar subcomplexes being Cohen-Macaulay allows for topological interpretations of certain positivity results about the chromatic polynomial due to N. Linial and I. M. Gessel.Pages: 311–329
Keywords: key words topological combinatorics; constructible complex; Cohen-Macaulay complex; chromatic polynomial
Full Text: PDF
References
1. A. Bj\ddot orner, “Topological methods,” in Handbook of Combinatorics, R. Graham, M. Gr\ddot otschel, and L. Lovász (Eds.), North-Holland/Elsevier, Amsterdam, 1995, pp. 1819-1872.
2. A. Bj\ddot orner and M. Wachs, “On lexicographically shellable posets,” Trans. Amer. Math. Soc. 277 (1983), 323-341.
3. R. Forman, “Morse theory for cell complexes,” Adv. Math. 134 (1998), 90-145.
4. I.M. Gessel, “Acyclic orientations and chromatic generating functions,” Discrete Math. 232 (2001), 119-130.
5. D. Gebhard and B. Sagan, “Sinks in acyclic orientations of graphs,” J. Combin. Theory, Ser. B, 80 (2000) 130-146.
6. C. Greene and T. Zaslavsky, “On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs,” Trans. Amer. Math. Soc. 280 (1983), 97-126.
7. J. Herzog, V. Reiner, and V. Welker, “The Koszul property in affine semigroup rings,” Pacific J. Math. 186 (1998), 39-65.
8. M. Hochster, “Rings of invariants of tori, Cohen-Macaulay rings generated by monomials, and polytopes,” Ann. Math. 96 (1972), 318-337.
9. A. Lempel, S. Even, and I. Cederbaum, “An algorithm for planarity testing of graphs,” Theory of Graphs, Gordon and Breach (Eds.), 1967, pp. 215-232.
10. N. Linial, “Graph coloring and monotone functions on posets,” Discrete Math. 58 (1986), 97-98.
11. L. Lovász, Combinatorial Problems and Exercises, 2nd edition, North-Holland, Amsterdam, 1993.
12. J.R. Munkres, Elements of Algebraic Topology, Menlo Park, CA, Addison-Wesley, 1984.
13. G. Reisner, “Cohen-Macaulay quotients of polynomial rings,” Adv. Math. 21 (1976), 30-49.
14. R.P. Stanley, “Acyclic orientations of graphs,” Discrete Math. 5 (1973), 171-178.
15. R.P. Stanley, “Generalized h-vectors, intersection cohomology of toric varieties, and related results,” in Commutative Algebra and Combinatorics, M. Nagata and H. Matsumura (Eds.), Advanced Studies in Pure Mathematics 11, Kinokuniya, Tokyo, and North-Holland, Amsterdam/New York, 1987, pp. 187-213.
16. R.P. Stanley, Combinatorics and Commutative Algebra, 2nd edition, Progress in Mathematics, vol. 41, Birkh\ddot auser, Boston/Basel/Stuttgart, 1996.
17. E. Steingrímsson, “The coloring ideal and coloring complex of a graph,” J. Alg. Comb. 14 (2001), 73-84.
2. A. Bj\ddot orner and M. Wachs, “On lexicographically shellable posets,” Trans. Amer. Math. Soc. 277 (1983), 323-341.
3. R. Forman, “Morse theory for cell complexes,” Adv. Math. 134 (1998), 90-145.
4. I.M. Gessel, “Acyclic orientations and chromatic generating functions,” Discrete Math. 232 (2001), 119-130.
5. D. Gebhard and B. Sagan, “Sinks in acyclic orientations of graphs,” J. Combin. Theory, Ser. B, 80 (2000) 130-146.
6. C. Greene and T. Zaslavsky, “On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs,” Trans. Amer. Math. Soc. 280 (1983), 97-126.
7. J. Herzog, V. Reiner, and V. Welker, “The Koszul property in affine semigroup rings,” Pacific J. Math. 186 (1998), 39-65.
8. M. Hochster, “Rings of invariants of tori, Cohen-Macaulay rings generated by monomials, and polytopes,” Ann. Math. 96 (1972), 318-337.
9. A. Lempel, S. Even, and I. Cederbaum, “An algorithm for planarity testing of graphs,” Theory of Graphs, Gordon and Breach (Eds.), 1967, pp. 215-232.
10. N. Linial, “Graph coloring and monotone functions on posets,” Discrete Math. 58 (1986), 97-98.
11. L. Lovász, Combinatorial Problems and Exercises, 2nd edition, North-Holland, Amsterdam, 1993.
12. J.R. Munkres, Elements of Algebraic Topology, Menlo Park, CA, Addison-Wesley, 1984.
13. G. Reisner, “Cohen-Macaulay quotients of polynomial rings,” Adv. Math. 21 (1976), 30-49.
14. R.P. Stanley, “Acyclic orientations of graphs,” Discrete Math. 5 (1973), 171-178.
15. R.P. Stanley, “Generalized h-vectors, intersection cohomology of toric varieties, and related results,” in Commutative Algebra and Combinatorics, M. Nagata and H. Matsumura (Eds.), Advanced Studies in Pure Mathematics 11, Kinokuniya, Tokyo, and North-Holland, Amsterdam/New York, 1987, pp. 187-213.
16. R.P. Stanley, Combinatorics and Commutative Algebra, 2nd edition, Progress in Mathematics, vol. 41, Birkh\ddot auser, Boston/Basel/Stuttgart, 1996.
17. E. Steingrímsson, “The coloring ideal and coloring complex of a graph,” J. Alg. Comb. 14 (2001), 73-84.