Strong weighting conjecture for nice uniform hypergraphs

From papers

Let HH be a nice rr-uniform hypergraph, where r3r\geq 3. A weight function is a map ω:E{1,,w}\omega:E\to\{1,\dots,w\}, inducing the vertex-coloring c:VNc:V\to\mathbb{N} by

c(v)=evω(e).c(v)=\sum_{e\ni v}\omega(e).

The coloring is strong if the vertices in every edge receive pairwise distinct colors, and HH is strongly ww-weighted if some such weight function induces a strong coloring.

Strong weighting conjecture. For every r3r\geq 3, there is a constant w=w(r)w=w(r) such that each nice rr-uniform hypergraph is strongly ww-weighted.

The conjecture proposes a general upper bound for strong weightings, after the paper's NP-completeness result for deciding strong 2-weightedness. The source further notes lower bounds on any such ww for infinitely many and for all values of rr, but does not resolve the conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Patrick Bennett, Andrzej Dudek, Alan Frieze and Laars Helenius, “Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs”, arXiv:1511.04569 (2015).

Solutions 0

No solutions have been posted yet.