2002/01/01 by Jiřı́ Fiala, Jan Kratochvı́l · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems #Mathematics #Combinatorics #Discrete mathematics
paper · doi:10.7151/dmgt.1159
openalex publication_date 2002/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
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.