Counterexamples clarify limits of bipanchromatic hypergraph colorings
Counterexamples to a conjecture and improved bounds for bipanchromatic colorings
Discrete Mathematics
Summary
This paper studies a special way to color hypergraphs so that every color appears at least twice, called the bipanchromatic number. The authors found the smallest example that proves a previous conjecture about this number is false. They also provide new bounds and show how certain parameters directly influence whether the original conjecture holds. Their work tightens the understanding of how these colorings behave in hypergraphs with minimum vertices and edges.
What this means in practice
- •For graph algorithm developers: Identify precise limits and bounds for coloring schemes in hypergraphs used by algorithms, improving theoretical guarantees.
- •For network designers: Use refined coloring constraints to model resource allocation and conflict avoidance in multi-link network topologies.
A theory result. No direct application yet.
Authors
Stefan Novaković, Duško Jojić
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$.