- Tytuł:
- Partial covers of graphs
- Autorzy:
-
Fiala, Jirí
Kratochvíl, Jan - Powiązania:
- https://bibliotekanauki.pl/articles/743545.pdf
- Data publikacji:
- 2002
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
covering projection
computational complexity
graph homomorphism - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 89-99
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł