Weak and strong versions of the 1-2-3 conjecture uniform hypergraphs

作者：Bennett Patrick^*; Dudek Andrzej; Frieze Alan; Helenius Laars

来源：Electronic Journal of Combinatorics, 2016, 23(2): P2.46.

Given an r-uniform hypergraph H = (V, E) and a weight function omega : E -> {1, ..., w}, a coloring of vertices of H, induced by w, is defined by c(v) = Sigma(e is an element of v) w(e) for all v is an element of V. If there exists such a coloring that is strong (that means in each edge no color appears more than once), then we say that H is strongly w-weighted. Similarly, if the coloring is weak (that means there is no monochromatic edge), then we say that H is weakly w-weighted. In this paper, we show that almost all 3 or 4-uniform hypergraphs are strongly 2-weighted (but not 1-weighted) and almost all 5-uniform hypergraphs are either 1 or 2 strongly weighted (with a nontrivial distribution). Furthermore, for r >= 6 we show that almost all r-uniform hypergraphs are strongly 1-weighted. We complement these results by showing that almost all 3-uniform hypergraphs are weakly 2-weighted but not 1-weighted and for r >= 4 almost all r uniform hypergraphs are weakly 1-weighted. These results extend a previous work of Addario-Berry, Dalal and Reed for graphs. We also prove general lower bounds and show that there are r-uniform hypergraphs which are not strongly (r(2) - r)- weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete.

• 出版日期2016-6-10