Weight choosability of oriented hypergraphs

Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk

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.


Keywords


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

Full Text:

PDF


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

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications