Monomial invariants applied to graph coloring

2019/10/10 by Guillermo Alesandroni, Alesandroni, Guillermo
Mathematics · #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics #math.AC #math.CO

paper · pdf · doi:10.48550/arxiv.1910.04896

arxiv created 2019/10/10 · arxiv updated 2019/10/14

Abstract

This article is built upon three main ideas. First, for a class of monomial ideals, it is proven that the multiplicity of an ideal equals the number of realizations of its codimension (an intuitive concept that we define later). Next, for an arbitrary graph G, we construct a monomial ideal M_G, and show that the chromatic number of G is equal to the codimension of M_G. Finally, for a class of graphs, we give a formula that computes the chromatic polynomial of G, evaluated at the chromatic number of G, in terms of the codimension and multiplicity of M_G. In particular, the formula applies to all graphs satisfying the Erdos-Faber-Lovász conjecture.

Related

• The Coloring Ideal and Coloring Complex of a Graph
• The combinatorial calculation of algebraic invariants of a monomial ideal
• Monomial multiplicities in explicit form
• Monomial invariants in codimension two
• Trees, parking functions, syzygies, and deformations of monomial ideals