A split graph counterexample disproves the biclique partition conjecture for split graphs, with an infinite family of examples and a solution to the singular n-tournament binary rank problem.
Improved Bounds for Multicovering Hypergraphs
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
The minimum number of bicliques needed to cover the edge set of the complete graph on $n$ vertices is $\lceil \log_2 n \rceil$. The Graham-Pollak theorem states that at least $n-1$ bicliques are required to partition the edge set of the complete graph on $n$ vertices. In this paper, we provide improvements for the generalizations of coverings of graphs and hypergraphs for some specific multiplicities. We also study an extension of the Katona-Szemer\'edi theorem to $r$-uniform hypergraphs.
fields
math.CO 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
f(n,k) satisfies (1+o(1)) c1(k) n^{1/(⌈k/2⌉+1)} ≤ f(n,k) ≤ (1+o(1)) c2(k) n^{1/(⌊k/2⌋+1)+o(1)} for fixed k≥2.
citing papers explorer
-
A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems
A split graph counterexample disproves the biclique partition conjecture for split graphs, with an infinite family of examples and a solution to the singular n-tournament binary rank problem.
-
Almost balanced ordered biclique covering of graphs
f(n,k) satisfies (1+o(1)) c1(k) n^{1/(⌈k/2⌉+1)} ≤ f(n,k) ≤ (1+o(1)) c2(k) n^{1/(⌊k/2⌋+1)+o(1)} for fixed k≥2.