Geodesic
Partial covers of graphs
Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 89-99

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: covering projection, computational complexity, graph homomorphism 
@article{DMGT_2002_22_1_a6,
     author = {Fiala, Jir{\'\i} and Kratochv{\'\i}l, Jan},
     title = {Partial covers of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {89--99},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a6/}
}
TY  - JOUR
AU  - Fiala, Jirí
AU  - Kratochvíl, Jan
TI  - Partial covers of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2002
SP  - 89
EP  - 99
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a6/
LA  - en
ID  - DMGT_2002_22_1_a6
ER  - 
%0 Journal Article
%A Fiala, Jirí
%A Kratochvíl, Jan
%T Partial covers of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2002
%P 89-99
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a6/
%G en
%F DMGT_2002_22_1_a6
Fiala, Jirí; Kratochvíl, Jan. Partial covers of graphs. Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 89-99. http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a6/