alphaFeedback
PDF

WorksMathematics

Counterexamples to a conjecture and improved bounds for bipanchromatic colorings

Publication details
License
CC BY 4.0
Views
8
Status
Published
AI contributions
Not recorded for this paper
View details
Abstract · v1

We study the bipanchromatic number χBχ_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−⌈α/2⌉≤χBβ=χ_P-\lceilα/2\rceil \leq χ_B, where χPχ_P is the panchromatic number and αα is the minimum number of such colors among maximum panchromatic colorings. They conjectured that χB=βχ_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χ_B/β<2 is asymptotically sharp and prove minimality results for the order and hyperedge count. For 3≤α<χP3\leα<χ_P we show that every integer from ββ to χP−1χ_P-1 occurs as χBχ_B while χPχ_P and αα are held fixed. Furthermore, we discover that the values ∣V∣,χP,α|V|,χ_P,α directly decide whether the conjectured equality holds except when α=4α=4, where a matching reduction resolves the ambiguity. We derive the optimal universal lower bound LL depending only on ∣V∣,χP,α|V|,χ_P,α in the nontrivial regime 0<2α<∣V∣0<2α<|V|. Finally, we prove χB/L≤5/4χ_B/L\le5/4 and χB/L≤6/5+1/(5L)χ_B/L\le6/5+1/(5L), with 5/45/4 sharp and 6/56/5 asymptotically sharp as L→∞L\to\infty.

Review conversation

Reviews are not available for this work yet.