A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems
This resolves a conjecture in graph theory, showing the proposed extension of the Graham-Pollak theorem does not hold, which is incremental but clarifies theoretical limits.
The authors tackled the open problem of whether the biclique partition number equals the number of maximal cliques in the complement minus one for co-chordal or split graphs, providing a counterexample with a split graph and constructing an infinite family of counterexamples.
The biclique partition number of a graph \(G\), denoted \( \operatorname{bp}(G)\), is the minimum number of biclique subgraphs needed to partition the edge set of $G$. Lyu and Hicks \cite{lyu2023finding} posed the open problem of whether \( \operatorname{bp}(G) = \operatorname{mc}(G^c) - 1 \) holds for every co-chordal graph or split graph, where \( \operatorname{mc}(G^c) \) denotes the number of maximal cliques in the complement of \( G \). Such a result would extend the celebrated Graham--Pollak theorem to a more general class of graphs. In this note, we answer this problem in the negative by providing a counterexample using a split graph. We also construct an infinite family of counterexamples and prove some structural properties of biclique partitions of split graphs. Finally, we solve an open problem posed by Siewert \cite{siewert2000biclique} on the existence of singular \(n\)-tournaments with binary rank \(n\).