Biclique-free graph

They arise in incidence problems in discrete geometry, and have also been used in parameterized complexity.

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 + m − t + 1) edges, where n and m are the numbers of vertices on each side of its bipartition.

[3] 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.

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.