Gröbner bases and graph colorings. (English) Zbl 0819.05029

Summary: We explore applications of computational methods in commutative algebra to graph theory. We give an explicit universal Gröbner basis for the radical ideal of a family of linear subspace arrangements related to chromatic numbers. We describe how to apply Gröbner bases to enumerate colorings. We also discuss similar results for a family of zero dimensional ideals.


05C15 Coloring of graphs and hypergraphs
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Full Text: EuDML EMIS