Counterexamples to a conjecture and improved bounds for bipanchromatic colorings

Source abstract

We study the bipanchromatic number $χ_B$, introduced by Lalou et al. (Discrete Appl. Math. 391 (2026), 511-522) as the maximum number of colors in a panchromatic hypergraph coloring where every color appears at least twice. They show that merging uniquely occurring colors in a maximum panchromatic coloring gives the lower bound $β=χ_P-\lceilα/2\rceil \leq χ_B$, where $χ_P$ is the panchromatic number and $α$ is the minimum number of such colors among maximum panchromatic colorings. They conjectured that $χ_B=β$ and subsequently disproved it (arXiv:2610.08042). We identify the smallest counterexample, with six vertices and three hyperedges, both minimum possible. We show that the ratio bound $χ_B/β<2$ is asymptotically sharp and prove minimality results for the order and hyperedge count. For $3\leα<χ_P$ we show that every integer from $β$ to $χ_P-1$ occurs as $χ_B$ while $χ_P$ and $α$ are held fixed. Furthermore, we discover that the values $|V|,χ_P,α$ directly decide whether the conjectured equality holds except when $α=4$, where a matching reduction resolves the ambiguity. We derive the optimal universal lower bound $L$ depending only on $|V|,χ_P,α$ in the nontrivial regime $0<2α<|V|$. Finally, we prove $χ_B/L\le5/4$ and $χ_B/L\le6/5+1/(5L)$, with $5/4$ sharp and $6/5$ asymptotically sharp as $L\to\infty$.