Weight choosability of oriented hypergraphs
Marcin Anholcer , Bartłomiej Bosek , Jarosław Grytczuk
AbstractThe 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.
|Journal series||Ars Mathematica Contemporanea, ISSN 1855-3966, e-ISSN 1855-3974, (N/A 100 pkt)|
|Publication size in sheets||0.5|
|Keywords in English||riented hypergraphs, 1-2-3 conjecture, combinatorial nullstellensatz, list weighting|
|ASJC Classification||; ; ;|
|Score||= 100.0, 02-04-2020, ArticleFromJournal|
|Publication indicators||= 0; : 2018 = 1.274; : 2018 = 0.91 (2) - 2018=0.887 (5)|
|Uwagi||First online 19 September 2018|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.