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

Original · EN

Given an r-uniform hypergraph H=(V,E) and a weight function ω:E→{1,,w}, a coloring of vertices of H, induced by ω, is defined by c(v) = ∑e v w(e) for all v∈ 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²-r)-weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete.