Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the combinatorial nullstellensatz

DOI10.1007/S10623-021-00859-7zbMATH Open1496.05052arXiv2007.00685OpenAlexW3137941486WikidataQ113903987 ScholiaQ113903987MaRDI QIDQ2168069FDOQ2168069

Authors: Oliver Janzer, Zoltán Lóránt Nagy 

Publication date: 31 August 2022

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Abstract: The long-standing ErdH{o}s-Faber-Lov'asz 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 ErdH{o}s-Faber-Lov'asz 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.

Full work available at URL: https://arxiv.org/abs/2007.00685

Recommendations

• On edge coloring of hypergraphs and Erdős-Faber-Lovász conjecture
• A proof of the Erdős-Faber-Lovász conjecture
• A remark on the conjecture of Erdös, Faber and Lovász
• Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
• Adding evidence to the Erdős-Faber-Lovász conjecture

zbMATH Keywords

hypergraphscoloringcombinatorial nullstellensatzgraph orientationsErdős-Faber-Lovász conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• On the combinatorial problems which I would most like to see solved
• Combinatorial Nullstellensatz
• Problems and results in combinatorial analysis and graph theory
• Partitions of nonzero elements of a finite field into pairs
• A new approach to constant term identities and Selberg-type integrals
• A generalization of combinatorial Nullstellensatz
• Colorings and orientations of graphs
• Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• The Erdős-Faber-Lovász conjecture for dense hypergraphs
• On edge coloring of hypergraphs and Erdős-Faber-Lovász conjecture
• The Erdős-Faber-Lovász conjecture is true for \(n \leq 12\)
• A note on Erdős-Faber-Lovász conjecture and edge coloring of complete graphs.
• Adding evidence to the Erdős-Faber-Lovász conjecture
• On the Erdős-Faber-Lovász Conjecture.
• The Erdős-Faber-Lovász conjecture -- the uniform regular case
• A note on the Erdős--Farber--Lovász conjecture
• A fractional version of the Erdős-Faber-Lovász conjecture
• The Alon-Tarsi number of planar graphs
• Packing nearly-disjoint sets
• On a Conjecture of Erdös, Faber, and Lovász about n-Colorings
• Combinatorial Nullstellensatz and DP-coloring of graphs
• Advances on the Erdős-Faber-Lovász conjecture
• Edge-coloring linear hypergraphs with medium-sized edges

Cited In (4)

• Title not available (Why is that?)
• Combinatorial Nullstellensatz
• Graph and hypergraph colouring via nibble methods: a survey
• On edge coloring of hypergraphs and Erdős-Faber-Lovász conjecture

This page was built for publication: Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the combinatorial nullstellensatz

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2168069)