# Biclique-free graph

In graph theory, a branch of mathematics, a t-biclique-free graph is a graph that has no 2t-vertex complete bipartite graph Kt,t as a subgraph. A family of graphs is biclique-free if there exists a number t such that the graphs in the family are all t-biclique-free. The biclique-free graph families form one of the most general types of sparse graph family. They arise in incidence problems in discrete geometry, and have also been used in parameterized complexity.

## Properties

### Sparsity

According to the Kővári–Sós–Turán theorem, every n-vertex t-biclique-free graph has O(n2 − 1/t) edges, significantly fewer than a dense graph would have.[1] Conversely, if a graph family is defined by forbidden subgraphs or closed under the operation of taking subgraphs, and does not include dense graphs of arbitrarily large size, it must be t-biclique-free for some t, for otherwise it would include large dense complete bipartite graphs.

As a lower bound, Erdős, Hajnal & Moon (1964) conjectured that every maximal t-biclique-free bipartite graph (one to which no more edges can be added without creating a t-biclique) has at least (t − 1)(n + mt + 1) edges, where n and m are the numbers of vertices on each side of its bipartition.[2]

### Relation to other types of sparse graph family

A graph with degeneracy d is necessarily (d + 1)-biclique-free. Additionally, any nowhere dense family of graphs is biclique-free. More generally, if there exists an n-vertex graph that is not a 1-shallow minor of any graph in the family, then the family must be n-biclique-free, because all n-vertex graphs are 1-shallow minors of Kn,n. In this way, the biclique-free graph families unify two of the most general classes of sparse graphs.[3]

## Applications

### Discrete geometry

In discrete geometry, many types of incidence graph are necessarily biclique-free. As a simple example, the graph of incidences between a finite set of points and lines in the Euclidean plane necessarily has no K2,2 subgraph.[4]

### Parameterized complexity

Biclique-free graphs have been used in parameterized complexity to develop algorithms that are efficient for sparse graphs with suitably small input parameter values. In particular, finding a dominating set of size k, on t-biclique-free graphs, is fixed-parameter tractable when parameterized by k + t, even though there is strong evidence that this is not possible using k alone as a parameter. Similar results are true for many variations of the dominating set problem.[3] It is also possible to test whether one dominating set of size at most k can be converted to another one by a chain of vertex insertions and deletions, preserving the dominating property, with the same parameterization.[5]

## References

1. ^ Kővári, T.; T. Sós, V.; Turán, P. (1954), "On a problem of K. Zarankiewicz" (PDF), Colloquium Math., 3: 50–57, MR 0065617. This work concerns the number of edges in biclique-free bipartite graphs, but a standard application of the probabilistic method transfers the same bound to arbitrary graphs.
2. ^ Erdős, P.; Hajnal, A.; Moon, J. W. (1964), "A problem in graph theory" (PDF), The American Mathematical Monthly, 71: 1107–1110, doi:10.2307/2311408, MR 0170339.
3. ^ a b Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah; Ferragina, Paolo, Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings, Lecture Notes in Computer Science, 7501, Springer, pp. 802–812, doi:10.1007/978-3-642-33090-2_69.
4. ^ Kaplan, Haim; Matoušek, Jiří; Sharir, Micha (2012), "Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique", Discrete and Computational Geometry, 48 (3): 499–517, arXiv:1102.5391, doi:10.1007/s00454-012-9443-3, MR 2957631. See in particular Lemma 3.1 and the remarks following the lemma.
5. ^ Lokshtanov, Daniel; Mouawad, Amer E.; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket (2015), "Reconfiguration on sparse graphs", in Dehne, Frank; Sack, Jörg-Rüdiger; Stege, Ulrike, Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings (PDF), Lecture Notes in Computer Science, 9214, Springer, pp. 506–517, arXiv:1502.04803, doi:10.1007/978-3-319-21840-3_42.