\(C_4\)-saturated bipartite graphs (Q1861219)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(C_4\)-saturated bipartite graphs |
scientific article |
Statements
\(C_4\)-saturated bipartite graphs (English)
0 references
16 March 2003
0 references
The authors consider the problem of finding subgraphs of the complete bipartite graph \(K_{m,n}\) which do not contain a subgraph isomorphic to a copy of \(K_{s,t}\) and are maximal with respect to this property. They translate this problem to the terminology of partial block designs. Their main interest concerns the case of \(s=t=2\) in which they apply some simple facts from the design theory to give alternate proofs of some classic asymptotic results on the Zarankiewicz problem due to Bollobás.
0 references
Zarankiewicz problem
0 references
bipartite graph
0 references
partial \(t\)-design
0 references