Existence of minimal uncolorable uniform bi-hypergraphs

From papers

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 r3r\ge 3, every bi-hypergraph in BiHyp(n,r)Bi\mathcal{H}yp(n,r) is colorable when rn(r1)2r\le n\le (r-1)^2, while minimal uncolorable bi-hypergraphs are known to exist at n=(r1)2+1n=(r-1)^2+1 in the complete case.

Existence conjecture. For any n,rNn,r\in \mathbb{N} with r3r\ge 3 and n(r1)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.

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

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

Solutions 0

No solutions have been posted yet.