The Coloring Ideal and Coloring Complex of a Graph
| dc.creator | Steingrimsson, Einar | |
| dc.date | 2001-04-05 | |
| dc.date.accessioned | 2026-07-07T04:41:01Z | |
| dc.date.available | 2026-07-07T04:41:01Z | |
| dc.description | 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-k(n)$ of the chromatic polynomial $k$ 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$. | |
| dc.description | 13 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/math/0104063 | |
| dc.identifier | http://arxiv.org/abs/math/0104063 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/61242 | |
| dc.subject | Combinatorics | |
| dc.subject | Rings and Algebras | |
| dc.title | The Coloring Ideal and Coloring Complex of a Graph | |
| dc.type | text |