Complete bipartite factorisations by complete bipartite graphs
Let \(K_{m,n}\) be the complete bipartite graph on sets of size \(m\) and \(n\). A \(K_{p,q}\)-factor of \(K_{m,n}\) is a spanning subgraph of \(K_{m,n}\) which is a union of vertex-disjoint subgraphs each isomorphic to \(K_{p,q}\). If \(K_{m,n}\) is expressed as a edge-disjoint union of \(K_{p,q}\)-factors, then this union is called a \(K_{p,q}\)-factorization of \(K_{m,n}\). Several basic arithmetic conditions are derived which must be satisfied if there exists such a factorization. The author conjectures that these conditions are also sufficient for the existence of a factorization. Tessellations of the plane by rectangles are used to prove the conjecture in many cases. In particular, the conjecture is proved for \(K_{1,q}\)-factorizations of \(K_{n,n}\) except for \(q= 4k+1\) and for a certain family of \(K_{1,3}\)-factorizations.
scientific article; zbMATH DE number 1018534