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

DOI10.1007/S10623-021-00859-7MaRDI QIDQ2168069zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(4)

• Combinatorial Nullstellensatz
• Graph and hypergraph colouring via nibble methods: a survey
• On edge coloring of hypergraphs and Erdős-Faber-Lovász conjecture
• scientific article; zbMATH DE number 5546 (Why is no real title available?)

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)