A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917387846025216 |
|---|---|
| author | Babu, Anand Jacob, Ashwin |
| author_facet | Babu, Anand Jacob, Ashwin |
| contents | 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\). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05491 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems Babu, Anand Jacob, Ashwin Combinatorics Discrete Mathematics 05C35, 90C10 G.2.1; G.2.2 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\). |
| title | A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems |
| topic | Combinatorics Discrete Mathematics 05C35, 90C10 G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2604.05491 |