Английская Википедия:Biclique-free graph
In graph theory, a branch of mathematics, a Шаблон:Mvar-biclique-free graph is a graph that has no Шаблон:Mvar-vertex complete bipartite graph Шаблон:Math as a subgraph. A family of graphs is biclique-free if there exists a number Шаблон:Mvar such that the graphs in the family are all Шаблон:Mvar-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 Шаблон:Mvar-vertex Шаблон:Mvar-biclique-free graph has Шаблон:Math 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 Шаблон:Mvar-biclique-free for some Шаблон:Mvar, for otherwise it would include large dense complete bipartite graphs.
As a lower bound, Шаблон:Harvtxt conjectured that every maximal Шаблон:Mvar-biclique-free bipartite graph (one to which no more edges can be added without creating a Шаблон:Mvar-biclique) has at least Шаблон:Math edges, where Шаблон:Mvar and Шаблон:Mvar are the numbers of vertices on each side of its bipartition.[2]
Relation to other types of sparse graph family
A graph with degeneracy Шаблон:Mvar is necessarily Шаблон:Math-biclique-free. Additionally, any nowhere dense family of graphs is biclique-free. More generally, if there exists an Шаблон:Mvar-vertex graph that is not a 1-shallow minor of any graph in the family, then the family must be Шаблон:Mvar-biclique-free, because all Шаблон:Mvar-vertex graphs are 1-shallow minors of Шаблон:Math. 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 Шаблон:Math 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 Шаблон:Mvar, on Шаблон:Mvar-biclique-free graphs, is fixed-parameter tractable when parameterized by Шаблон:Math, even though there is strong evidence that this is not possible using Шаблон:Mvar 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 Шаблон:Mvar can be converted to another one by a chain of vertex insertions and deletions, preserving the dominating property, with the same parameterization.[5]
References
- ↑ Шаблон:Citation. 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.
- ↑ Шаблон:Citation.
- ↑ 3,0 3,1 Шаблон:Citation.
- ↑ Шаблон:Citation. See in particular Lemma 3.1 and the remarks following the lemma.
- ↑ Шаблон:Citation.
