Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


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).

Abstract

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:http://dx.doi.org/10.1007/978-3-642-13073-1_25
Record Created:07 Oct 2010 12:05
Last Modified:03 Apr 2013 13:20

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library