Partial covers of graphs
Jiřı́ Fiala, Jan Kratochvı́l · Discussiones Mathematicae Graph Theory · 2002
Given graphs G and H, a mapping f : V (G) → V (H) is a homomorphism if (f(u), f(v)) is an edge of H for every edge (u, v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of deciding existence of partial covers and of full covers (locally bijective homomorphisms), which were previously studied.