A hypergraph is properly 2-colorable if each vertex can be colored by one of two colors and no edge is completely colored by a single color. We present a complete algebraic characterization of the 2-colorability of r-uniform hypergraphs. This generalizes a well known algebraic characterization of k-colorability of graphs due to Alon, Tarsi, Lovasz, de Loera, and Hillar. We also introduce a method for distinguishing proper 2-colorings called coloring schemes, and provide a decomposition of all proper 2-colorings into these schemes.As an application, we present a new example of a 4-uniform non-2-colorable hypergraph on 11 vertices and 24 edges which is not isomorphic to a well-known construction by Seymour (1974) of a minimal non-2-colorable 4-uniform hypergraph. Additionally, we provide a heuristically constructed hypergraph which admits only specific coloring schemes. Further, we give an algebraic characterization of the coloring scheme known as a conflict-free coloring. A corrigendum was added to this paper on June 3, 2024.
@article{10_37236_8205,
author = {Michael Krul and Lubo\v{s} Thoma},
title = {2-colorability of \(r\)-uniform hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {3},
doi = {10.37236/8205},
zbl = {1418.05066},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8205/}
}
TY - JOUR
AU - Michael Krul
AU - Luboš Thoma
TI - 2-colorability of \(r\)-uniform hypergraphs
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/8205/
DO - 10.37236/8205
ID - 10_37236_8205
ER -
%0 Journal Article
%A Michael Krul
%A Luboš Thoma
%T 2-colorability of \(r\)-uniform hypergraphs
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8205/
%R 10.37236/8205
%F 10_37236_8205
Michael Krul; Luboš Thoma. 2-colorability of \(r\)-uniform hypergraphs. The electronic journal of combinatorics, Tome 26 (2019) no. 3. doi: 10.37236/8205
