An Algebraic Formulation of Hypergraph Colorings

Abstract

A hypergraph is properly vertex-colored if no edge contains vertices which are assigned the same color. We provide an algebraic formulation of the $k$-colorability of uniform and non-uniform hypergraphs. This formulation provides an algebraic algorithm, via Gröbner bases, which can determine whether a given hypergraph is $k$-colorable or not. We further study new families of k-colorings with additional restrictions on permissible colorings. These new families of colorings generalize several recently studied variations of $k$-colorings.