Complete bipartite factorisations by complete bipartite graphs
type: Item
instance of: scholarly article
title: Complete bipartite factorisations by complete bipartite graphs
zbMATH Open document ID: 0878.05066
DOI: 10.1016/S0012-365X(97)00248-3
published in: Discrete Mathematics
publication date: 1998-01-05T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05B45
zbMATH DE Number: 1018534
zbMATH Keywords: tessellations of the plane
zbMATH Keywords: complete bipartite graph
zbMATH Keywords: factorization
author: Nigel Martin
reviewed by: Konrad Engel
MaRDI profile type: Publication
cites work: Bipartite designs
cites work: \(P_ 3\)-factorization of complete bipartite graphs
cites work: Q3976650
cites work: An Introduction to Matroid Theory
full work available at URL: s0012-365x(97)00248-3
OpenAlex ID: W2088385043
description: scientific article; zbMATH DE number 1018534