Counterexamples to a conjecture and improved bounds for bipanchromatic colorings
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−⌈α/2⌉ ≤ χ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≤α<χ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≤5/4 and χB/L≤6/5+1/(5L), with 5/4 sharp and 6/5 asymptotically sharp as L→∞.
Related
- Improved bounds for the two-point logarithmic Chowla conjecture
- Improved bounds for Szpiro's conjecture
- Improved Bounds on the Szeged-Wiener Gap and the BKLPS Conjecture
- Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
- Linear bounds for rich-neighbor edge-colorings
BibTeX
@misc{novakovic2026counterexamples,
title = {{Counterexamples to a conjecture and improved bounds for bipanchromatic colorings}},
author = {Stefan Novaković and Duško Jojić},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27133},
eprint = {2610.27133},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27133},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Counterexamples to a conjecture and improved bounds for bipanchromatic colorings
AU - Stefan Novaković
AU - Duško Jojić
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.27133
UR - https://arxiv.org/abs/2610.27133
AB - 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−⌈α/2⌉ ≤ χ_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≤α<χ_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≤5/4 and χ_B/L≤6/5+1/(5L), with 5/4 sharp and 6/5 asymptotically sharp as L→∞.
ER -