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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1159,
author = {Jir\'\i\ Fiala and Jan Kratochv\'\i l},
title = {Partial covers of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {22},
year = {2002},
pages = {89-99},
zbl = {1017.05094},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1159}
}
Jirí Fiala; Jan Kratochvíl. Partial covers of graphs. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 89-99. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1159/
[000] [1] J. Abello, M.R. Fellows and J.C. Stillwell, On the complexity and combinatorics of covering finite complexes, Australian Journal of Combinatorics 4 (1991) 103-112. | Zbl 0763.05035
[001] [2] D. Angluin, Local and global properties in networks of processors, in: Proceedings of the 12th ACM Symposium on Theory of Computing (1980) 82-93.
[002] [3] H.L. Bodlaender, The classification of coverings of processor networks, Journal of Parallel Distributed Computing 6 (1989) 166-182, doi: 10.1016/0743-7315(89)90048-8.
[003] [4] N. Biggs, Algebraic Graph Theory (Cambridge University Press, 1974).
[004] [5] G.J. Chang and D. Kuo, The L(2,1)-labeling problem on graphs, SIAM J. Disc. Math. 9 (1996) 309-316, doi: 10.1137/S0895480193245339. | Zbl 0860.05064
[005] [6] B. Courcelle and Y. Métivier, Coverings and minors: Applications to local computations in graphs, European Journal of Combinatorics 15 (1994) 127-138, doi: 10.1006/eujc.1994.1015. | Zbl 0788.05076
[006] [7] M. Dyer and C. Greenhill, The complexity of counting graph homomorphisms, in: Proceedings of the Eleventh annual ACM-SIAM Symposium on Discrete Algorithms SODA'00 (San Francisco, 2000). | Zbl 0965.68073
[007] [8] J. Fiala, Locally injective homomorphism (Doctoral Thesis, Charles University, Praque 2000).
[008] [9] J. Fiala and J. Kratochvíl, Complexity of partial covers of graphs, in: Algorithms and Computation, 12th ISAAC'01, Christchurch, New Zealand, Lecture Notes in Computer Science 2223 (Springer Verlag, 2001) 537-549. | Zbl 1077.68725
[009] [10] J. Fiala, J. Kratochvíl and T. Kloks, Fixed-parameter complexity of λ-labelings, Discrete Applied Math. 113 (1) (2001) 59-72, doi: 10.1016/S0166-218X(00)00387-5. | Zbl 0982.05085
[010] [11] J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Disc. Math. 5 (1992) 586-595, doi: 10.1137/0405048. | Zbl 0767.05080
[011] [12] J.L. Gross and T.W. Tucker, Topological Graph Theory (J. Wiley and Sons, 1987).
[012] [13] J.L. Gross and T.W. Tucker, Generating all graph coverings by permutation voltage assignments, Discrete Math. 18 (1977) 273-283, doi: 10.1016/0012-365X(77)90131-5. | Zbl 0375.55001
[013] [14] P. Hell and J. Nesetril, On the complexity of H-coloring, J. Combin. Theory (B) 48 (1990) 92-110, doi: 10.1016/0095-8956(90)90132-J. | Zbl 0639.05023
[014] [15] P. Hell and J. Nesetril, The core of a graph, Discrete Math. 109 (1992) 117-126, doi: 10.1016/0012-365X(92)90282-K. | Zbl 0803.68080
[015] [16] J. van den Heuvel, R.A. Leese and M.A. Shepherd, Graph labeling and radio channel assignment, Journal of Graph Theory 29 (4) (1998) 263-283, doi: 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V | Zbl 0930.05087
[016] [17] J. Kratochvíl, A. Proskurowski and J.A. Telle, Covering regular graphs, J. Combin. Theory (B) 71 (1997) 1-16, doi: 10.1006/jctb.1996.1743. | Zbl 0895.05049
[017] [18] J. Kratochvíl, A. Proskurowski and J.A. Telle, Complexity of graph covering problems, Nordic Journal of Computing 5 (1998) 173-195. | Zbl 0911.68076
[018] [19] J. Kratochvíl, A. Proskurowski and J.A. Telle, Covering directed multigraphs I. Colored directed multigraphs, in: Graph-Theoretical Concepts in Computer Science, Proceedings 23rd WG '97, Berlin, Lecture Notes in Computer Science 1335 (Springer Verlag, 1997) 242-254. | Zbl 0890.68095
[019] [20] R.A. Leese, A fresh look at channel assignment in uniform networks, EMC97 Symposium, Zurich, 127-130.
[020] [21] F.T. Leighton, Finite common coverings of graphs, J. Combin. Theory (B) 33 (1982) 231-238, doi: 10.1016/0095-8956(82)90042-9. | Zbl 0488.05033
[021] [22] W. Massey, Algebraic Topology: An Introduction (Harcourt, Brace and World, 1967).
[022] [23] K.-Ch. Yeh, Labeling graphs with a condition at distance two, Ph.D. Thesis (University of South Carolina, 1990).