Details

Autor(en) / Beteiligte

• Janzer, Oliver
• Nagy, Zoltán Lóránt

Titel

Coloring linear hypergraphs: the Erdős–Faber–Lovász conjecture and the Combinatorial Nullstellensatz

Ist Teil von

• Designs, codes, and cryptography, 2022-09, Vol.90 (9), p.1991-2001

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2022

Quelle

SpringerLink (Online service)

Beschreibungen/Notizen

• The long-standing Erdős–Faber–Lovász 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 Erdős–Faber–Lovász 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.