Counterexamples to a conjecture and improved bounds for bipanchromatic colorings

Introduction

A panchromatic coloring [1, 2, 3, 4] uses every color in every hyperedge, with maximum $\chi_P$ colors. Lalou et al. [1] introduced bipanchromatic colorings to study completely independent spanning trees in split graphs. These colorings use each color at least twice overall, with maximum $\chi_B$. Let $\alpha$ be the minimum number of colors occurring once in a $\chi_P$-coloring. Their conjecture [1 Conjecture 1] predicts $\chi_B = \chi_P - \lceil\alpha/2\rceil$ by merging those colors.

The same authors subsequently disproved this conjecture [5]. They construct counterexamples as three-hyperedge sunflowers with a common set of $6d$ vertices and three disjoint petals of size $q$, where $d \ge1$ and $q \ge2d$. Their parameters are $\chi_P = 6d + q$, $\alpha= 6d$, and $\chi_B = 4d + q$. Thus the conjectured value is exceeded by exactly $d$, on $6d + 3q \ge12d$ vertices. Our three-hyperedge construction uses $12d - 6$ vertices for the same excess (Proposition 2).

Without restricting the number of hyperedges, we prove that the minimum order is $4d + 2$ and classify all examples attaining it (Theorem 6). Their family has actual-to-conjectured ratio at most $6/5$. We determine the sharp worst-case ratio over all hypergraphs, proving that it is strictly below two and can approach two (Theorem 5). We develop the coloring bounds and equality criteria suggested in their concluding remarks [5 Section 5].

Sections 2–3 introduce the colorings and counterexamples. Section 4 establishes sharp bounds and characterizes minimum-size counterexamples. Section 5 determines, with minimum order, all possible $\chi_B$ values with fixed $\chi_P$ and $\alpha$, showing that no formula depending only on $\chi_P$ and $\alpha$ can determine $\chi_B$ for every hypergraph. Section 6 shows that the hypergraph order, $\chi_P$ and $\alpha$ determine if the conjectured equality holds, except when $\alpha= 4$ which is resolved by maximum matching. In Section 7, the optimal lower bound $L$ for $\chi_B$ is determined from $|V|$, $\chi_P$ and $\alpha$, with $\chi_B/L \le5/4$ and $\chi_B/L \le6/5 + 1/(5L)$, where $5/4$ is sharp and $6/5$ is asymptotically sharp as $L \to\infty$.

Preliminaries

A hypergraph $H=(V,\mathcal{E})$ consists of a non-empty set $V=V(H)$ (the vertices of $H$) and a hyperedge set $E(H)=\mathcal{E}\subset\mathcal{P}(V)$. If every hyperedge of $H$ contains exactly $r$ vertices, $H$ is $r$-uniform. A proper coloring of a hypergraph assigns colors to its vertices so that no hyperedge of size at least two is monochromatic.

Observe that $\chi_B(H)=\max\{k\in\mathbb{N}:\alpha_k=0\}$. Since every color appears on at least two vertices, it follows that $\chi_B(H)\le\lfloor|V|/2\rfloor$.

When the hypergraph $H$ is implied, we omit the argument $H$ and write $\chi_P$, $\chi_B$, and $\alpha_k$. Write $\alpha=\alpha_{\chi_P}$. Lalou et al. [1 Conjecture 1] conjectured that

This equality was disproved in [5 Proposition 1]. For $|V|\ge2$, choose a panchromatic $\chi_P$-coloring with $\alpha$ unique colors. Merge the unique colors in pairs. If one unique color remains, merge it with any other color. This results in a bipanchromatic coloring with $\chi_P-\lceil\alpha/2\rceil$ colors. Thus, $\chi_P-\lceil\alpha/2\rceil$ is a lower bound for $\chi_B$. The equality in [1 Conjecture 1] would mean that this merging procedure is optimal. The examples in § 3 have bipanchromatic colorings with more colors than this procedure produces. We define excess $\epsilon=\chi_B-(\chi_P-\lceil\alpha/2\rceil)$ which measures the difference between $\chi_B$ and the lower bound in (1).

Counterexamples

The sunflower $S_n=(V,\mathcal{E})$ is an $(n+1)$-uniform hypergraph with $2n$ vertices and $n$ hyperedges. The set of vertices is $V=S\sqcup P$, where $S=\{s_1,\ldots,s_n\}$ and $P=\{p_1,\ldots,p_n\}$ are disjoint, and its hyperedges are $e_i=S\cup\{p_i\}$ for all $i\in[n]$.

Consequently, $\epsilon=\lceil n/2\rceil-1\ge1$, so every $S_n$ is a counterexample to [1 Conjecture 1]. In particular, for every $n\in\mathbb{N}$, $S_{2n+1}$ has $4n+2$ vertices, $2n+1$ hyperedges, and $\epsilon(S_{2n+1})=n$.

Proof. We can color each $s_i$ by $i$, and all $p_i$ by $n+1$. This is a panchromatic coloring (Figure 1(a)), and $\chi_P=n+1$. Any panchromatic $(n+1)$-coloring of $S_n$ uses each color only once per hyperedge $S\sqcup\{p_i\}$. The colors on $S$ have to be unique, thus $\alpha=|S|=n$ and every $p_i$ has the same color. Merging the unique colors gives $n+1-\left\lceil\frac{n}{2}\right\rceil$ colors (Figure 1(b)). However, we can color each $\{s_i,p_i\}$ distinctly (Figure 1(c)). Each hyperedge then contains $n$ colors, none of which is unique. Notice that $\chi_B\leq|V|/2=n$, thus $\chi_B=n$ and $\epsilon=\left\lfloor\frac{n}{2}\right\rfloor-1$.

Thus, the gap between $\chi_B$ and the quantity in [1 Conjecture 1] is unbounded. In particular, adding any fixed constant to the right-hand side cannot make the conjecture valid in general.

Figure 1(a) shows a $\chi_P$-coloring of $S_n$ attaining $\alpha$. Figure 1(b) shows a bipanchromatic coloring obtained by merging unique colors. Figure 1(c) shows a bipanchromatic coloring with more colors.

For excess $n$, the three-hyperedge construction in [5 Proposition 1] uses at least $12n$ vertices. The following construction uses $12n-6$. It is obtained by enlarging $S_3$. Replace each vertex by a group of $2n-1$ vertices and each hyperedge by the union of the groups corresponding to its vertices.

Bounds and minimality

Consider an arbitrary hypergraph $H$ with panchromatic number $\chi_P$. For any integer $k\leq\chi_P$, let $\beta_k=k-\left\lceil\frac{\alpha_k}{2}\right\rceil$. In particular, let $\beta=\beta_{\chi_P}$. [1 Conjecture 1] asserts that $\chi_B=\beta$, but this does not hold in general. However, for any $k$-panchromatic coloring of $H$ attaining $\alpha_k$, the pairing argument used in [1] produces a bipanchromatic coloring with $\beta_k$ colors. Thus, for every $k\leq\chi_P$ we obtain a lower bound for $\chi_B$, and the largest of these bounds equals $\chi_B$.

Proof. (i) Corollary 3 gives $\chi_{B} \ge\beta$. If $\alpha= 0$, a $\chi_{P}$-coloring is already bipanchromatic, so $\chi_{B} = \chi_{P} = \beta$. If $\alpha> 0$, no $\chi_{P}$-coloring is bipanchromatic, so $\chi_{B} \le\chi_{P} - 1$. For $\alpha\in\{1,2\}$, $\chi_{B} = \beta$. If $\alpha= \chi_{P}$, then $|V| = \chi_{P}$, so $\chi_{B} \le\lfloor|V|/2 \rfloor= \lfloor\chi_{P}/2 \rfloor= \beta$, so $\chi_{B} = \beta$.

(ii) By (i), $3 \le\alpha\le\chi_{P} - 1$. Thus $\beta\ge\chi_{P} - \left\lceil\frac{\chi_{P}-1}{2} \right\rceil= \left\lfloor\frac{\chi_{P}}{2} \right\rfloor$. Corollary 3 gives $\beta< \chi_{B}$, and $\alpha> 0$ gives $\chi_{B} \le\chi_{P} - 1$ as above. $\square$

Let $\rho= \chi_{B}/\beta$ denote the actual-to-conjectured ratio.

Proof. By Lemma 4 it holds that $\rho\ge1$, with equality precisely when (1) is true. Suppose that $\chi_{P} \ge2$. If $\rho\ne1$, then Lemma 4(ii) gives the upper bound. For $n \ge3$, Theorem 1 gives $\rho(S_{n}) = \frac{\chi_{P}-1}{\lceil\chi_{P}/2 \rceil}$. The sharp bounds are strictly below 2 and tend to 2 as $\chi_{P} \to\infty$. $\square$

The order of a hypergraph $H$ is the number of its vertices $|V(H)|$. We show $S_{2n+1}$ has minimum order among hypergraphs satisfying $\epsilon\ge n$.

Proof. By Lemma 4(ii), $\beta\ge\lceil\chi_{P}/2 \rceil$ and $\chi_{B} \le\chi_{P} - 1$. Hence

Thus, $\chi_{B} \ge2n+1$, and consequently $|V| \ge2\chi_{B} \ge4n+2 = |V(S_{2n+1})|$.

Suppose that $\epsilon(H) = n$ and $|V| = 4n+2$. It follows from (3) that $\chi_{B} = 2n+1$ and $\beta= \lceil\chi_{P}/2 \rceil= n+1$. Since $\chi_{P} \ne\chi_{B}$ ($\epsilon> 0$), we obtain $\chi_{P} = 2n+2$. Moreover, $\left\lceil\frac{\alpha}{2} \right\rceil= \chi_{P} - \beta= n+1$. Since $\alpha\ne\chi_{P}$ it follows that $\alpha= 2n+1$.

Consider a panchromatic $(\chi_{P},\alpha)$-coloring of $H$, and let $S$ be the set of its $\alpha$ uniquely colored vertices. All remaining $|V|-\alpha$ vertices have a common color $C$. For every vertex $v$ of color $C$, there is a hyperedge $S \sqcup\{v\}$. Otherwise, if every hyperedge containing $v$ also contained another vertex of $v$’s color, recoloring $v$ with an existing unique color preserves panchromaticity and contradicts the supposed $\alpha$. Removing hyperedges that properly contain other hyperedges leaves $S_{2\epsilon+1}$.

Every counterexample has at least three hyperedges. Choose a $\chi_{P}$-coloring attaining $\alpha$. If every non-unique color occurred twice, then $|V| = 2\chi_{P} - \alpha$, so $\chi_{B} \le\lfloor|V|/2 \rfloor= \beta$, a contradiction. Thus some color $C$ occurs on at least three vertices. Since $\alpha> 0$, the same recoloring argument shows that each such vertex is the only $C$-colored vertex in some hyperedge. These hyperedges are distinct.

Proposition 2 attains this three-hyperedge minimum with $\epsilon(\Delta_{n}) = n$ for every $n \ge1$. However, Theorem 6 implies that every hypergraph of minimum order satisfying $\epsilon(H) \ge n$ has at least $2n+1$ hyperedges. Thus, for $n \ge2$, the minimum numbers of vertices and hyperedges cannot be attained simultaneously.

Nondetermination

By Corollary 3 and Lemma 4, if $\chi_P > \alpha\ge3$, then $\chi_P - \lceil\alpha/2\rceil\le\chi_B < \chi_P$. We will show that every integer value of $\chi_B$ in this range can be realized for the given pair $(\chi_P,\alpha)$. Thus, $\chi_B$ cannot be expressed as a function of $\chi_P$ and $\alpha$ alone.

The construction realizes the prescribed parameters using at most $\alpha$ hyperedges, each of size $\chi_P$. Together with Lemma 4(i), this shows that $\chi_P$ and $\alpha$ uniquely determine $\chi_B$ only when $\alpha\in\{0,1,2,\chi_P\}$.

The minimum number of vertices in a hypergraph $H$ with prescribed feasible parameters $(\chi_P,\alpha,\chi_B)$ is $\max\{2\chi_P-\alpha,2\chi_B\}$. Indeed, a $\chi_P$-coloring attaining $\alpha$ gives $|V| \ge\alpha+ 2(\chi_P-\alpha) = 2\chi_P-\alpha$. A bipanchromatic $\chi_B$-coloring also gives $|V| \ge2\chi_B$.

For $3\leq\alpha<\chi_P$, the construction in Proposition 7 has exactly $\max\{2\chi_P-\alpha,2\chi_B\}$ vertices.

In the remaining cases, Lemma 4(i) gives $\chi_B=\beta$. Take two sets of size $\chi_P$ intersecting in $\alpha$ vertices, use them as hyperedges, and take their union as the vertex set. When $\alpha=\chi_P$, this gives just one hyperedge. The panchromatic number is $\chi_P$, and every maximum panchromatic coloring has unique colors precisely on the $\alpha$ common vertices. The same lemma therefore gives bipanchromatic number $\beta$. This construction has $2\chi_P-\alpha=\max\{2\chi_P-\alpha,2\beta\}$ vertices, attaining the lower bound.

Characterization of equality

Here we discuss conditions characterizing $\chi_B=\beta$ (equivalently $\epsilon=0$) for an arbitrary hypergraph.

Proof. Assume that $\chi_B=\beta$ and consider a $(\chi_P,\alpha)$-coloring of $H$. Let $n=3$ if $\alpha$ is odd and $n=4$ otherwise. If a color $C$ occurs at least $n$ times, recolor all vertices of color $C$ with $n$ existing unique colors, using each at least once. Merge the remaining $\alpha-n$ uniquely colored vertices in pairs. This yields a $\beta+1$ bipanchromatic coloring of $H$, contradicting $\chi_B=\beta$. Therefore, if $\alpha$ is odd, then every color occurs at most twice, and if $\alpha$ is even, every color occurs at most thrice. If two distinct colors each occur three times, recolor their six vertices with six colors that are used only once (since $\alpha\geq6$), and then merge the remaining uniquely colored vertices in pairs, again obtaining a coloring with $\beta+1$ colors. Thus, at most one color occurs thrice, so $|V|\in\{2\chi_P-\alpha,2\chi_P-\alpha+1\}$, and $\lfloor|V|/2\rfloor=\beta$.

The converse follows from the definition.

For a hypergraph $H$ with $\alpha=4$, the equality $\chi_B=\beta$ requires further consideration. Consider mutually disjoint sets $|S|=4$, $\{v,a,b,x_0,x_1,x_2\}$ and $|P_i|=2$ for $i=1,2,3$. We define two hypergraphs $H_-$ and $H_+$ whose hyperedge sets are, respectively

Notice that $|V(H_-)|=|V(H_+)|=10$, $\chi_P(H_-)=\chi_P(H_+)=6$, and $\alpha(H_-)=\alpha(H_+)=4$. However, $\beta=\chi_B(H_-)=4<|V|/2$ and $\beta<\chi_B(H_+)=5=|V|/2$.

Therefore, if $\alpha(H)=4$, we need an additional analysis. For a given hypergraph $H=(V,\mathcal{E})$, define a simple graph $G_H=(V,E)$, where

Proof. Since $\alpha=4$ and $\beta=\chi_P-2$, then $\chi_B\in\{\chi_P-2,\chi_P-1\}$. Consider any bipanchromatic $k$-coloring. Each color occurring exactly twice determines an edge of $G_H$. These edges are vertex-disjoint, so they form a matching in $G_H$. Therefore, we have at most $\nu$ colors used exactly two times. Consequently, $|V|\ge2\nu+3(k-\nu)$, so $k\le\chi_B\le\lfloor(|V|+\nu)/3\rfloor$.

If $|V|+\nu\le3\chi_P-4$, then $\chi_B\le\chi_P-2=\beta$, and therefore $\epsilon=0$.

For the converse, assume $\epsilon=0$ and choose a panchromatic $\chi_P$-coloring attaining $\alpha=4$. If some color $C$ occurs at least four times, we can recolor all vertices of color $C$ with the four colors that are used only once. This produces a bipanchromatic coloring with $\chi_P-1$ colors, contradicting $\epsilon=0$.

Therefore, every color is used at most three times. Let $C_k$ denote the number of colors used exactly $k$ times. Then, $\chi_P=4+C_2+C_3$, and $|V|=4+2C_2+3C_3$.

The pairs corresponding to the $C_2$ color classes must form a maximum matching in $G_H[V\setminus S]$, where $S$ is the set of vertices receiving the four unique colors. Otherwise, an augmenting path would yield a larger matching, whose pairs could be assigned distinct colors in a panchromatic coloring of $H$ (the pairs intersect every hyperedge). The endpoints $u$ and $v$ of such an augmenting path belong to three-vertex color classes $C_3$. Reassign the colors so that each matching pair forms its own color class. If $u$ and $v$ belong to the same three-vertex color class, assign the color of one of the four uniquely colored vertices to the third vertex of that class. This produces a $\chi_P$-coloring with three uniquely colored vertices, a contradiction. If $u$ and $v$ belong to different three-vertex color classes, assign the four unique colors to their other four vertices. This produces a bipanchromatic coloring with $\chi_P-1$ colors, again a contradiction, since $\chi_B=\beta=\chi_P-2$. Thus, $\nu\le C_2+4$, and thus

Given $H$ and promises $\chi_P$ and $\alpha$, $\epsilon=0$ (or $\chi_B=\beta$) is decidable in polynomial time.

Order-aware improved bounds

In this section, we introduce another lower bound $L$ for the bipanchromatic number, based on our construction, and show that $\beta\le L\le\chi_B$. Thus, $L$ improves the lower bound $\beta$.

Consider a hypergraph $H=(V,\mathcal{E})$ with $|V|\ge2$ and $\alpha>0$. If $\alpha\ge|V|/2$, then $\chi_B=\lfloor|V|/2\rfloor$. Indeed, the unique vertices can be paired with the non-unique vertices, and any remaining vertices can be assigned colors so that every color used occurs at least twice. For the sunflower $S_n$ (see Theorem 1), where $n\ge3$, we have $\alpha=|V|/2$ and $\chi_B=|V|/2$, while $\chi_B/\beta\to2$ as $n\to\infty$.

We now consider the case $0<\alpha<|V|/2$ and choose a panchromatic $\chi_P$-coloring of $H$ with $\alpha$ unique colors. Let $m=\chi_P-\alpha$ denote the number of colors used more than once. Suppose that color $i$ is used on $c_i$ vertices, where

Observe that $c_1+c_2+\cdots+c_m=|V|-\alpha$.

Let $d\in[m]$ be the smallest index such that $c_1+c_2+\cdots+c_d\ge\alpha$. Such an integer exists because $|V|-\alpha>\alpha$. Recolor all vertices in the first $d$ color classes with the $\alpha$ unique colors so that each of these colors is used at least twice. This yields a bipanchromatic coloring of $H$ with $L_d = \chi_P - d$ colors.

Since $c_i \ge2$ for every $i$, we have $d \le\lceil\alpha/2 \rceil$. Consequently, $\chi_B \ge L_d = \chi_P - d \ge\beta$.

To obtain a bound for $d$, write Euclidean division of $|V|-\alpha$ by $m=\chi_P-\alpha$ as:

Define

Unlike $L_d$, which uses the chosen coloring, $L$ depends only on $|V|$, $\chi_P$, and $\alpha$.

Remark. If the three-hyperedge family described in [5 Proposition 1] satisfies $0<\alpha<|V|/2$, then its parameters considered in Proposition 10 are $q=3$, $r=0$, and $D=\alpha/3$. Thus $L=\chi_P-\alpha/3=\chi_B$. The boundary case $2\alpha=|V|$ is covered by the observation at the start of this section. So, our order-aware bound gives the exact bipanchromatic number throughout that family.

Let $U=\min\{\chi_P-1,\lfloor|V|/2\rfloor\}$. If $0<\alpha<|V|/2$, then $\beta\le L\le L_d\le\chi_B\le U$, and $U$ is an upper bound for $\chi_B$.

Now, we examine the relations between $U$, $\chi_B$, and $L$.

Proof. Use the balanced sequence $\hat{c}_1,\ldots,\hat{c}_m$ from Proposition 10. These are not necessarily the actual color-class sizes of $H$. Their sum is $|V|-\alpha$, and $D$ is the least index for which the first $D$ terms sum to at least $\alpha$.

Set $g=U-L\ge0$. We prove that $L\ge5g-1$. Since $U\le\chi_P-1=L+D-1$, we obtain $g\le D-1$. By minimality of $D$, it follows that

Consequently,

Since $\sum_{i=1}^{m}\hat{c}_i=|V|-\alpha$, and $\hat{c}_i\le\hat{c}_D$ for $i\ge D$,

Since $U=L+g=\alpha+m-D+g$ and $U\le|V|/2$ (by definition), inequality (11) yields

We use $L=\alpha+m-D$ and $m-D\ge0$ to consider the following four cases:

$\hat{c}_D$	From (12)	From (10)	Conclusion
2	$g=0$	–	$L\ge5g-1$
3	$m-D\ge2g-2$	$\alpha\ge3g+1$	$L\ge5g-1$
4	$m-D\ge g-1$	$\alpha\ge4g+1$	$L\ge5g$
$\ge5$	–	$\alpha\ge5g+1$	$L\ge5g+1$

Therefore, $5g\le L+1$, which gives $5U\le6L+1$. For $L\le3$ we obtain $U=L$. For $L\ge4$,

□

Remark. The conclusions of Theorem 11 also hold with $L_d$ in place of $L$. Indeed, $L\le L_d\le\chi_B$, so $5U\le6L+1\le6L_d+1$ and $\chi_B/L_d\le\chi_B/L\le5/4$.

We prove that for fixed parameters $(|V|,\chi_P,\alpha)$, without more information, the bound $L$ is the best possible.

Proof. Compute $q$ and $r$ as before. Set $m=\chi_P-\alpha$ and consider pairwise disjoint sets $S,P_1,\ldots,P_q,Z$ with $|S|=\alpha$, $|P_i|=m$, and $|Z|=r$. Choose $R\subseteq P_1$ with $|R|=r$. We define the hypergraph $H=(V,\mathcal{E})$, where

Thus $|V|=\alpha+qm+r$ is attained, and every hyperedge has size $\chi_P$. Now, we define a coloring of $H$ such that $\alpha$ vertices in $S$ receive distinct colors, each $P_i$ uses all $m$ remaining colors once, and, if $r > 0$, each color from $R$ is used exactly once on $Z$. This gives a panchromatic coloring of $H$ with $\chi_P$ colors. In any panchromatic $\chi_P$-coloring of $H$, precisely the vertices in $S$ have unique colors, so $\alpha$ is attained.

Now, we consider a bipanchromatic $k$-coloring of $H$. Assume that precisely $s \le\alpha$ colors occur on $S$. Each of the other $k-s$ colors occurs in every $P_i$, so at least $q$ times. Those also absent from $P_1 \setminus R$ must occur on $Z$, so they occur at least $q+1$ times. At most $m-r$ of the $k-s$ colors occur on $P_1 \setminus R$. Therefore

Substituting $s \le\alpha$, $|V| = \alpha+ qm + r$, and $\chi_P = \alpha+ m$ gives

By the definition of $D$, it follows that

Thus every bipanchromatic coloring has at most $\chi_P-D=L$ colors. Since also $L \le\chi_B$ by Proposition 10, we obtain $\chi_B=L$.

Therefore, at every feasible triple in this range, any universally valid lower bound using only $(|V|,\chi_P,\alpha)$ is at most $L$. Since $L$ is itself valid, it is the strongest such lower bound.

Proof. For any $n \in\mathbb{N}$, Proposition 7 describes a hypergraph whose parameters $(|V|,\chi_P,\alpha,\chi_B)$ are $(12n-2,6n,3n+1,6n-1)$. Here we obtain $q=3$, $r=0$, $D=n+1$, and $L=5n-1$, so

This is $5/4$ at $n=1$ and tends to $6/5$ as $n \to\infty$. Proposition 12 confirms optimality.

AI Assistance

ChatGPT was used to assist with proof development. All AI-assisted arguments were reviewed and revised by the authors, who take full responsibility for the final manuscript.