Existence of minimal uncolorable uniform bi-hypergraphs

About 3 years old · traced to

Let BiHyp(n,r)Bi\mathcal{H}yp(n,r) be the set of rr-uniform bi-hypergraphs of order nn, and let MUC(n,r)\mathcal{MUC}(n,r) be the set of minimal uncolorable bi-hypergraphs in BiHyp(n,r)Bi\mathcal{H}yp(n,r). For r≥3r\ge 3, every bi-hypergraph in BiHyp(n,r)Bi\mathcal{H}yp(n,r) is colorable when r≤n≤(r−1)2r\le n\le (r-1)^2, while minimal uncolorable bi-hypergraphs are known to exist at n=(r−1)2+1n=(r-1)^2+1 in the complete case.

Existence conjecture. For any n,r∈Nn,r\in \mathbb{N} with r≥3r\ge 3 and n≥(r−1)2+1n\ge (r-1)^2+1, the set MUC(n,r)\mathcal{MUC}(n,r) is not empty.

This conjecture concerns the existence of minimal obstructions to proper coloring beyond the first possible uncolorable order and would provide a general response to the existence aspect of the problem posed by Tuza and Voloshin. The supplied text gives no resolution beyond the stated known colorability range.

References

Primary source

Meiqiao Zhang, Fengming Dong and Ruixue Zhang, “On the colorability of bi-hypergraphs”, arXiv:2310.06464 (2023).

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.