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.
@article{10_37236_9894,
author = {Michael Krul and Lubo\v{s} Thoma},
title = {An algebraic formulation of hypergraph colorings},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {2},
doi = {10.37236/9894},
zbl = {1529.05070},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9894/}
}
TY - JOUR
AU - Michael Krul
AU - Luboš Thoma
TI - An algebraic formulation of hypergraph colorings
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/9894/
DO - 10.37236/9894
ID - 10_37236_9894
ER -
%0 Journal Article
%A Michael Krul
%A Luboš Thoma
%T An algebraic formulation of hypergraph colorings
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9894/
%R 10.37236/9894
%F 10_37236_9894
Michael Krul; Luboš Thoma. An algebraic formulation of hypergraph colorings. The electronic journal of combinatorics, Tome 30 (2023) no. 2. doi: 10.37236/9894
