This record has been edited as far as possible, missing data will be added when the version of record is issued.
Coloring linear hypergraphs: the Erdos-Faber-Lovasz conjecture and the Combinatorial Nullstellensatz
- Journal Article
The long-standing Erdos-Faber-Lovasz conjecture states that every n-uniform linear hypergaph with n edges has a proper vertex-coloring using n colors. In this paper we propose an algebraic framework to the problem and formulate a corresponding stronger conjecture. Using the Combinatorial Nullstellensatz, we reduce the Erdos-Faber-Lovasz conjecture to the existence of non-zero coefficients in certain polynomials. These coefficients are in turn related to the number of orientations with prescribed in-degree sequences of some auxiliary graphs. We prove the existence of certain orientations, which verifies a necessary condition for our algebraic approach to work. Show more
Journal / seriesDesigns, Codes and Cryptography
SubjectColoring; Hypergraphs; Erdos-Faber-Lovasz; Combinatorial Nullstellensatz; Graph orientations
MoreShow all metadata