Partial covers of graphs

Jirí Fiala; Jan Kratochvíl

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 1, page 89-99
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Jirí Fiala, and Jan Kratochvíl. "Partial covers of graphs." Discussiones Mathematicae Graph Theory 22.1 (2002): 89-99. <http://eudml.org/doc/270598>.

@article{JiríFiala2002,
abstract = {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.},
author = {Jirí Fiala, Jan Kratochvíl},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {covering projection; computational complexity; graph homomorphism; lambda coloring},
language = {eng},
number = {1},
pages = {89-99},
title = {Partial covers of graphs},
url = {http://eudml.org/doc/270598},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Jirí Fiala
AU - Jan Kratochvíl
TI - Partial covers of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 1
SP - 89
EP - 99
AB - 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.
LA - eng
KW - covering projection; computational complexity; graph homomorphism; lambda coloring
UR - http://eudml.org/doc/270598
ER -

References

top
  1. [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. Zbl0763.05035
  2. [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. 
  3. [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. 
  4. [4] N. Biggs, Algebraic Graph Theory (Cambridge University Press, 1974). 
  5. [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. Zbl0860.05064
  6. [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. Zbl0788.05076
  7. [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). Zbl0965.68073
  8. [8] J. Fiala, Locally injective homomorphism (Doctoral Thesis, Charles University, Praque 2000). 
  9. [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. Zbl1077.68725
  10. [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. Zbl0982.05085
  11. [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. Zbl0767.05080
  12. [12] J.L. Gross and T.W. Tucker, Topological Graph Theory (J. Wiley and Sons, 1987). 
  13. [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. Zbl0375.55001
  14. [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. Zbl0639.05023
  15. [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. Zbl0803.68080
  16. [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 Zbl0930.05087
  17. [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. Zbl0895.05049
  18. [18] J. Kratochvíl, A. Proskurowski and J.A. Telle, Complexity of graph covering problems, Nordic Journal of Computing 5 (1998) 173-195. Zbl0911.68076
  19. [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. Zbl0890.68095
  20. [20] R.A. Leese, A fresh look at channel assignment in uniform networks, EMC97 Symposium, Zurich, 127-130. 
  21. [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. Zbl0488.05033
  22. [22] W. Massey, Algebraic Topology: An Introduction (Harcourt, Brace and World, 1967). 
  23. [23] K.-Ch. Yeh, Labeling graphs with a condition at distance two, Ph.D. Thesis (University of South Carolina, 1990). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.