We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Packing bipartite graphs with covers of complete bipartite graphs.

Chalopin, J. and Paulusma, Daniel (2010) 'Packing bipartite graphs with covers of complete bipartite graphs.', in Algorithms and complexity, 7th International Conference, CIAC 2010, 26-28 May 2010, Rome, Italy ; proceedings. Berlin ; Heidelberg: Springer, 276-287 . Lecture notes in computer science. (6078).


For a set of graphs, a perfect -packing (-factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of and that together contain all vertices of G. If G allows a covering (locally bijective homomorphism) to a graph H, then G is an H-cover. For some fixed H let consist of all H-covers. Let K k,ℓ be the complete bipartite graph with partition classes of size k and ℓ, respectively. For all fixed k,ℓ ≥ 1, we determine the computational complexity of the problem that tests if a given bipartite graph has a perfect -packing. Our technique is partially based on exploring a close relationship to pseudo-coverings. A pseudo-covering from a graph G to a graph H is a homomorphism from G to H that becomes a covering to H when restricted to a spanning subgraph of G. We settle the computational complexity of the problem that asks if a graph allows a pseudo-covering to K k,ℓ for all fixed k,ℓ ≥ 1.

Item Type:Book chapter
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:2010
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar