The biclique partition number of balanced split graphs: deciding $\mathrm{bp}(G)=\omega(G)-1$ versus $\mathrm{bp}(G)=\omega(G)$

The biclique partition number $\mathrm{bp}(G)$ is the minimum number of complete bipartite subgraphs (bicliques) whose edge sets partition the edge set of $G$. For split graphs — graphs whose vertices partition into a clique $K$ and a stable set $S$ — Lyu and Hicks proved $\mathrm{mc}(G^c)-2\le\mathrm{bp}(G)\le\mathrm{mc}(G^c)-1$, where $\mathrm{mc}(G^c)$ is the number of maximal cliques of the complement, and posed as an open problem whether $\mathrm{bp}(G)=\mathrm{mc}(G^c)-1$ always holds for co-chordal or split graphs, which would extend the Graham–Pollak theorem. Babu and Jacob first announced an affirmative answer for all split graphs, then withdrew it, and in April 2026 posted a counterexample: a 14-vertex balanced split graph with $\mathrm{bp}(G)=6=\mathrm{mc}(G^c)-2$, together with an infinite family. Their note settles unbalanced split graphs completely ($\mathrm{bp}(G)=\omega(G)-1$) and proves $\mathrm{bp}(G)\le\omega(G)$ for balanced split graphs, but leaves the balanced case open. The problem: for a balanced split graph — a split graph admitting a split partition $(K,S)$ into a clique $K$ and a stable set $S$ with $|K|=\omega(G)$ and $|S|=\alpha(G)$, equivalently $\omega(G)+\alpha(G)=|V(G)|$ — decide whether $\mathrm{bp}(G)=\omega(G)-1$ or $\mathrm{bp}(G)=\omega(G)$, and characterize structurally which bipartite adjacency between $K$ and $S$ forces each outcome. The problem is open.

Background

A biclique is a complete bipartite subgraph, and the biclique partition number $\mathrm{bp}(G)$ of a graph $G$ is the minimum number of bicliques whose edge sets partition the edge set of $G$. The celebrated Graham–Pollak theorem (1972) states that the edges of the complete graph $K_n$ cannot be partitioned into fewer than $n-1$ complete bipartite graphs, i.e. $\mathrm{bp}(K_n)=n-1$. A clique is a set of pairwise adjacent vertices (its maximum size is the clique number $\omega(G)$) and a stable set is a set of pairwise non-adjacent vertices (its maximum size is the independence number $\alpha(G)$). A split graph is a graph whose vertex set partitions into a clique $K$ and a stable set $S$; split graphs are exactly the graphs that are simultaneously chordal (no induced cycle longer than a triangle) and co-chordal (complement of a chordal graph). A maximal clique is a clique not contained in a larger one; write $\mathrm{mc}(G^c)$ for the number of maximal cliques of the complement $G^c$. For co-chordal graphs Lyu and Hicks proved $\mathrm{bp}(G)<\mathrm{mc}(G^c)$, and for split graphs the two-sided bound $\mathrm{mc}(G^c)-2\le\mathrm{bp}(G)\le\mathrm{mc}(G^c)-1$, with exact solvability when $G^c$ is chordal and clique-vertex irreducible (a restriction on how the maximal cliques of $G^c$ overlap); they posed as an open problem whether the equality $\mathrm{bp}(G)=\mathrm{mc}(G^c)-1$ holds for every co-chordal graph or split graph. This equality would be a genuine extension of Graham–Pollak, since for $G=K_n$ the complement is edgeless, $\mathrm{mc}(G^c)=n$, and the equality reads $\mathrm{bp}(K_n)=n-1$. Babu and Jacob first claimed the affirmative answer $\mathrm{bp}(G)=\mathrm{mc}(G^c)-1$ for all split graphs (arXiv:2507.08114, July 2025), but withdrew the preprint in March 2026 with the comment that a key lemma was 'not correct in its entirety'. In April 2026 they posted a counterexample note (arXiv:2604.05491): a 14-vertex balanced split graph with $\mathrm{bp}(G)=6=\omega(G)-1=\mathrm{mc}(G^c)-2$, plus an infinite family of such counterexamples. Here a balanced split graph is a split graph that admits a split partition $(K,S)$ with $|K|=\omega(G)$ and $|S|=\alpha(G)$, equivalently $\omega(G)+\alpha(G)=|V(G)|$; by the Hammer–Simeone trichotomy, every split partition of a split graph is of exactly one of three types — balanced ($|K|=\omega(G)$, $|S|=\alpha(G)$), $S$-max ($|K|=\omega(G)-1$, $|S|=\alpha(G)$), or $K$-max ($|K|=\omega(G)$, $|S|=\alpha(G)-1$) — so the split partition with $|K|=\omega(G)$ and $|S|=\alpha(G)$, the balanced split partition, is unique, and in it no vertex of $S$ is adjacent to all of $K$ and every vertex of $K$ has a neighbor in $S$. The Babu–Jacob counterexample and its infinite family are the symmetric case $\omega(G)=\alpha(G)$; the balanced class is strictly larger and also contains graphs with $\omega(G)\neq\alpha(G)$. For any balanced split graph one checks that the maximal cliques of $G^c$ are exactly $S$ together with $\{v\}\cup(S\setminus N_G(v))$ for each $v\in K$, where $N_G(v)$ denotes the set of neighbors of $v$ in $G$, so $\mathrm{mc}(G^c)=\omega(G)+1$; hence the Lyu–Hicks bounds and the note's Lemma 7 ($\mathrm{bp}(G)\le\omega(G)$ for balanced split graphs) pin the biclique partition number of a balanced split graph to the two values $\omega(G)-1$ and $\omega(G)$. Both values occur: the note's infinite family attains $\omega(G)-1$, while the 4-vertex path, viewed as a balanced split graph whose clique side is its middle edge and whose stable side is its two endpoints, has $\mathrm{bp}=2=\omega(G)$. The note settles the unbalanced case completely ($\mathrm{bp}(G)=\omega(G)-1=\mathrm{mc}(G^c)-1$, its Lemma 2) and proves structural restrictions on minimum biclique partitions of balanced split graphs (its Lemmas 3–6, among them: no biclique of a minimum partition is a star centered in $S$, and no biclique has one side lying entirely inside $S$), but does not determine which of the two values a given balanced split graph attains.

Problem Statement

Let $G$ be a balanced split graph, i.e. a split graph admitting a split partition $(K,S)$ into a clique $K$ and a stable set $S$ with $|K|=\omega(G)$ and $|S|=\alpha(G)$, equivalently $\omega(G)+\alpha(G)=|V(G)|$; this balanced split partition is unique, no vertex of $S$ is adjacent to all of $K$, and every vertex of $K$ has a neighbor in $S$. Published results pin its biclique partition number to $\omega(G)-1\le\mathrm{bp}(G)\le\omega(G)$, equivalently $\mathrm{bp}(G)\in\{\mathrm{mc}(G^c)-2,\mathrm{mc}(G^c)-1\}$. Determine which value it attains, by carrying out both of the following: (i) give a criterion that decides, for an arbitrary balanced split graph $G$, whether $\mathrm{bp}(G)=\omega(G)-1$ or $\mathrm{bp}(G)=\omega(G)$ — equivalently, whether the Lyu–Hicks equality $\mathrm{bp}(G)=\mathrm{mc}(G^c)-1$ holds for $G$; and (ii) characterize structurally the balanced split graphs that attain each of the two values — since the balanced split partition is unique, this structure is captured by the bipartite adjacency between the clique side $K$ and the stable side $S$.

References

1. Anand Babu and Ashwin Jacob, 'A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems', arXiv:2604.05491, 2026, DOI 10.48550/arXiv.2604.05491, https://arxiv.org/abs/2604.05491
2. Bochuan Lyu and Illya V. Hicks, 'Finding biclique partitions of co-chordal graphs', Discrete Applied Mathematics 337 (2023) 278–287, DOI 10.1016/j.dam.2023.05.001, https://doi.org/10.1016/j.dam.2023.05.001 (preprint arXiv:2203.02837, https://arxiv.org/abs/2203.02837)
3. Anand Babu and Ashwin Jacob, 'Exact Biclique Partition number of Split Graphs', arXiv:2507.08114, 2025 (v2 withdrawn March 2026), DOI 10.48550/arXiv.2507.08114, https://arxiv.org/abs/2507.08114
4. R. L. Graham and H. O. Pollak, 'On embedding graphs in squashed cubes', Lecture Notes in Mathematics (Graph Theory and Applications), 1972, pp. 99–110, DOI 10.1007/bfb0067362, https://doi.org/10.1007/bfb0067362
5. Peter L. Hammer and Bruno Simeone, 'The splittance of a graph', Combinatorica 1 (1981) 275–284, DOI 10.1007/bf02579333, https://doi.org/10.1007/bf02579333
6. Zhen-Peng Xu, Jie Wang, Qi Ye, Gereon Koßmann, René Schwonnek and Andreas Winter, 'Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs', arXiv:2511.13531, 2025, DOI 10.48550/arXiv.2511.13531, https://arxiv.org/abs/2511.13531
7. Bochuan Lyu and Illya V. Hicks, 'Maximal Clique and Edge-Ranking Bounds of Biclique Cover Number', arXiv:2302.12775, 2023, DOI 10.48550/arXiv.2302.12775, https://arxiv.org/abs/2302.12775