The Coloring Ideal and Coloring Complex of a Graph
Einar Steingrímsson
DOI: 10.1023/A:1011222121664
Abstract
Let G be a simple graph on d vertices. We define a monomial ideal K in the Stanley-Reisner ring A of the order complex of the Boolean algebra on d atoms. The monomials in K are in one-to-one correspondence with the proper colorings of G. In particular, the Hilbert polynomial of K equals the chromatic polynomial of G.
The ideal K is generated by square-free monomials, so A/K is the Stanley-Reisner ring of a simplicial complex C. The h-vector of C is a certain transformation of the tail T( n) = n d - 
( n) of the chromatic polynomial of G. The combinatorial structure of the complex C is described explicitly and it is shown that the Euler characteristic of C equals the number of acyclic orientations of G.
( n) of the chromatic polynomial of G. The combinatorial structure of the complex C is described explicitly and it is shown that the Euler characteristic of C equals the number of acyclic orientations of G.Pages: 73–84
Keywords: chromatic polynomial; monomial ideal; simplicial complex; Stanley-Reisner ring; Hilbert polynomial; Euler characteristic; acyclic orientations
Full Text: PDF
References
1. G. Almkvist, Europ. J. Combin., to appear.
2. F. Brenti, “Expansions of chromatic polynomials and log-concavity,” Trans. Amer. Math. Soc. 332(2) (1992), 729-756.
3. F. Brenti, “Hilbert polynomials in combinatorics,” J. Alg. Combin. 7(2) (1998), 127-156.
4. T.Y. Chow, “The path-cycle symmetric function of a digraph,” Adv. Math. 118(1) (1996), 71-98.
5. T.Y. Chow, “Descents, quasi-symmetric functions, Robinson-Schensted for posets and the chromatic symmetric function,” J. Alg. Combin. 10 (1999), 227-240.
6. F.R.K. Chung and R.L. Graham, “On the cover polynomial of a digraph,” J. Combin. Theory Ser. B 65(2) (1995), 273-290.
7. D. Grayson and M. Stillman, “MACAULAY2-a software system for algebraic geometry and commutative algebra,” available at http://www.math.uiuc.edu/Macaulay2.
8. R. Stanley, “Acyclic orientations of graphs,” Discrete Math. 5 (1973), 171-178.
9. R.P. Stanley, “A symmetric function generalization of the chromatic polynomial of a graph,” Adv. Math. 111(1) (1995), 166-194.
10. R. Stanley, Combinatorics and Commutative Algebra, 2nd edition, Birkh\ddot auser, Boston, 1996.
2. F. Brenti, “Expansions of chromatic polynomials and log-concavity,” Trans. Amer. Math. Soc. 332(2) (1992), 729-756.
3. F. Brenti, “Hilbert polynomials in combinatorics,” J. Alg. Combin. 7(2) (1998), 127-156.
4. T.Y. Chow, “The path-cycle symmetric function of a digraph,” Adv. Math. 118(1) (1996), 71-98.
5. T.Y. Chow, “Descents, quasi-symmetric functions, Robinson-Schensted for posets and the chromatic symmetric function,” J. Alg. Combin. 10 (1999), 227-240.
6. F.R.K. Chung and R.L. Graham, “On the cover polynomial of a digraph,” J. Combin. Theory Ser. B 65(2) (1995), 273-290.
7. D. Grayson and M. Stillman, “MACAULAY2-a software system for algebraic geometry and commutative algebra,” available at http://www.math.uiuc.edu/Macaulay2.
8. R. Stanley, “Acyclic orientations of graphs,” Discrete Math. 5 (1973), 171-178.
9. R.P. Stanley, “A symmetric function generalization of the chromatic polynomial of a graph,” Adv. Math. 111(1) (1995), 166-194.
10. R. Stanley, Combinatorics and Commutative Algebra, 2nd edition, Birkh\ddot auser, Boston, 1996.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition