Strong weighting conjecture for nice uniform hypergraphs
Strong weighting conjecture for nice uniform hypergraphs
Let be a nice -uniform hypergraph, where . A weight function is a map , inducing the vertex-coloring by
The coloring is strong if the vertices in every edge receive pairwise distinct colors, and is strongly -weighted if some such weight function induces a strong coloring.
Strong weighting conjecture. For every , there is a constant such that each nice -uniform hypergraph is strongly -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 for infinitely many and for all values of , 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
Sign in to submit a solution.
No solutions have been posted yet.