Skip to main content

Research Repository

Advanced Search

Packing bipartite graphs with covers of complete bipartite graphs

Chalopin, J.; Paulusma, D.

Authors

J. Chalopin



Contributors

Tiziana Calamoneri
Editor

Josep Diaz
Editor

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.

Citation

Chalopin, J., & Paulusma, D. (2010). Packing bipartite graphs with covers of complete bipartite graphs. In T. Calamoneri, & J. Diaz (Eds.), Algorithms and complexity, 7th International Conference, CIAC 2010, 26-28 May 2010, Rome, Italy ; proceedings (276-287). https://doi.org/10.1007/978-3-642-13073-1_25

Conference Name 7th International Conference on Algorithms and Complexity
Conference Location Rome, Italy
Publication Date Jan 1, 2010
Deposit Date Oct 6, 2010
Publisher Springer Verlag
Pages 276-287
Series Title Lecture notes in computer science
Series Number 6078
Edition 7th
Book Title Algorithms and complexity, 7th International Conference, CIAC 2010, 26-28 May 2010, Rome, Italy ; proceedings.
DOI https://doi.org/10.1007/978-3-642-13073-1_25
Public URL https://durham-repository.worktribe.com/output/1159326


You might also like



Downloadable Citations