Weight choosability of oriented hypergraphs

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


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.
Author Marcin Anholcer (WIiGE / KBO)
Marcin Anholcer,,
- Department of Operations Research
, Bartłomiej Bosek - Uniwersytet Jagielloński w Krakowie (UJ)
Bartłomiej Bosek,,
, Jarosław Grytczuk - Warsaw University of Technology (PW), MNiSW [80]
Jarosław Grytczuk,,
Journal seriesArs Mathematica Contemporanea, ISSN 1855-3966, e-ISSN 1855-3974, (N/A 100 pkt)
Issue year2019
Publication size in sheets0.5
Keywords in Englishriented hypergraphs, 1-2-3 conjecture, combinatorial nullstellensatz, list weighting
ASJC Classification2602 Algebra and Number Theory; 2607 Discrete Mathematics and Combinatorics; 2608 Geometry and Topology; 2614 Theoretical Computer Science
URL https://amc-journal.eu/index.php/amc/article/view/1317
Languageen angielski
Score (nominal)100
Score sourcejournalList
ScoreMinisterial score = 100.0, 02-04-2020, ArticleFromJournal
Publication indicators WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.274; WoS Impact Factor: 2018 = 0.91 (2) - 2018=0.887 (5)
Citation count*
Additional fields
UwagiFirst online 19 September 2018
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?