Weight choosability of oriented hypergraphs

Authors

  • Marcin Anholcer Poznań University of Economics and Business, Poland
  • Bartłomiej Bosek Jagiellonian University, Poland
  • Jarosław Grytczuk Warsaw University of Technology, Poland

DOI:

https://doi.org/10.26493/1855-3974.1317.745

Keywords:

Oriented hypergraphs, 1-2-3 conjecture, combinatorial nullstellensatz, list weighting

Abstract

The 1-2-3 conjecture states that every simple graph (with no isolated edges) has an edge weigthing by numbers 1, 2, 3 such that the resulting weighted vertex degrees form a proper coloring of the graph. We study a similar problem for oriented hypergraphs. We prove that every oriented hypergraph has an edge weighting satisfying a similar condition, even if the weights are to be chosen from arbitrary lists of size two. The proof is based on the Combinatorial Nullstellensatz and a theorem of Schur for permanents of positive semi-definite matrices. We derive several consequences of the main result for uniform hypergraphs. We also point on possible applications of our results to problems of 1-2-3 type for non-oriented hypergraphs.

Published

2018-09-19

Issue

Section

Articles