Packing bipartite graphs with covers of complete bipartite graphs
Jérémie Chalopin, Daniël Paulusma · Discrete Applied Mathematics · 2012
For a set S of graphs, a perfect S -packing ( S -factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of S and that together contain all vertices of G . If G allows a covering (locally bijective homomorphism) to a graph H , i.e., a vertex mapping f : V G → V H satisfying the property that f ( u ) f ( v ) belongs to E H whenever the edge u v belongs to E G such that for every u ∈ V G the restriction of f to the neighborhood of u is bijective, then G is an H -cover. For some fixed H let S ( H ) consist of all connected 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 whether a given bipartite graph has a perfect S ( K k , ℓ ) -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 whether a graph allows a pseudo-covering to K k , ℓ for all fixed k , ℓ ≥ 1 .