Bosek's asymptotic harmonious coloring conjecture for hypergraphs

About 3 years old · traced to

Let k,Δ≥2k,\Delta\geq 2. A harmonious coloring of a kk-uniform hypergraph HH is a vertex coloring that is rainbow on every edge and assigns distinct color sets to distinct edges; let h(H)h(H) be the least number of colors in such a coloring. If HH has mm edges and maximum degree Δ\Delta, then Bosek's conjecture. There exists a constant c=c(k,Δ)c=c(k,\Delta) such that

h(H)≤k!mk+c.h(H)\leq \sqrt[k]{k!m}+c.

The lower bound (rk)≤m\binom{r}{k}\leq m for a harmonious coloring using rr colors gives the leading-order term k!mk\sqrt[k]{k!m}, so the conjecture asks whether the known upper bound can be sharpened to this term up to an additive constant depending only on kk and Δ\Delta.

References

Primary source

Sebastian Czerwiński, “On harmonious coloring of hypergraphs”, arXiv:2301.00302 (2024).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.