×

zbMATH — the first resource for mathematics

Locally constrained graph homomorphisms – structure, complexity, and applications. (English) Zbl 1302.05122
Summary: A graph homomorphism is an edge preserving vertex mapping between two graphs. Locally constrained homomorphisms are those that behave well on the neighborhoods of vertices. If the neighborhood of any vertex of the source graph is mapped bijectively (injectively, surjectively) to the neighborhood of its image in the target graph, the homomorphism is called locally bijective (injective, surjective, respectively). We show that this view unifies issues studied before from different perspectives and under different names, such as graph covers, distance constrained graph labelings, or role assignments. Our survey provides an overview of applications, complexity results, related problems, and historical notes on locally constrained graph homomorphisms.

MSC:
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
MathOverflow Questions:
Regular graph colorings
Software:
nauty
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abello, J.; Fellows, M.R.; Stillwell, J.C., On the complexity and combinatorics of covering finite complexes, Australian journal of combinatorics, 4, 103-112, (1991) · Zbl 0763.05035
[2] D. Angluin, Local and global properties in networks of processors, in: Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, pp. 82-93
[3] Angluin, D.; Gardiner, A., Finite common coverings of pairs of regular graphs, Journal of combinatorial theory B, 30, 184-187, (1981) · Zbl 0426.05044
[4] Archdeacon, D., A Kuratowski theorem for the projective plane, Journal of graph theory, 5, 243-246, (1981) · Zbl 0464.05028
[5] Archdeacon, D., Two graphs without planar covers, Journal of graph theory, 41, 4, 318-326, (2002) · Zbl 1018.05022
[6] Aspvall, B.; Plass, M.F.; Tarjan, R.E., A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Information processing letters, 8, 121-123, (1979) · Zbl 0398.68042
[7] Biggs, N., Algebraic graph theory, (1974), Cambridge University Press · Zbl 0284.05101
[8] Bodlaender, H.L., The classification of coverings of processor networks, Journal of parallel and distributed computing, 6, 166-182, (1989)
[9] Boldi, P.; Vigna, S., Fibrations of graphs, Discrete mathematics, 243, 1-3, 21-66, (2002) · Zbl 0988.05073
[10] J. Chalopin, D. Paulusma, Graph labelings derived from models in distributed computing, in: Fomin [27], pp. 301-312 · Zbl 1167.68399
[11] Corneil, D.; Gotlieb, C., An efficient algorithm for graph isomorphism, Journal of the association for computing machinery, 17, 51-64, (1970) · Zbl 0199.27801
[12] D.G. Corneil, Graph Isomorphism, Ph.D. Thesis, University of Toronto, 1968
[13] Courcelle, B.; Métivier, Y., Coverings and minors: applications to local computations in graphs, European journal of combinatorics, 15, 127-138, (1994) · Zbl 0788.05076
[14] Cvetković, D.M.; Doob, M.; Sachs, H., ()
[15] Djoković, D.Ž, Automorphisms of graphs and coverings, Journal of combinatorial theory B, 16, 243-247, (1974)
[16] Everett, M.G.; Borgatti, S., Role colouring a graph, Mathematical social sciences, 21, 2, 183-188, (1991) · Zbl 0771.05037
[17] Feder, T.; Vardi, M.Y., The computational structure of momotone monadic SNP andconstraint satisfaction: A study through Datalog and group theory, SIAM journal of computing, 1, 57-104, (1998) · Zbl 0914.68075
[18] M. Fellows, Planar emulators and planar covers, manuscript, 1989
[19] J. Fiala, Graph covers, Master’s thesis, Charles University, Prague, 1997 (in Czech)
[20] Fiala, J.; Kratochvíl, J., Complexity of partial covers of graphs, (), 537-549 · Zbl 1077.68725
[21] Fiala, J.; Kratochvíl, J., Partial covers of graphs, Discussiones mathematicae graph theory, 22, 89-99, (2002) · Zbl 1017.05094
[22] J. Fiala, J. Kratochvíl, Locally injective graph homomorphism: Lists guarantee dichotomy, in: Fomin [27], pp. 15-26 · Zbl 1167.68406
[23] Fiala, J.; Kratochvíl, J.; Kloks, T., Fixed-parameter complexity of \(\lambda\)-labelings, Discrete applied mathematics, 113, 1, 59-72, (2001) · Zbl 0982.05085
[24] Fiala, J.; Kratochvíl, J.; Pór, A., On the computational complexity of partial covers of theta graphs, Discrete applied mathematics, 156, 1143-1149, (2008) · Zbl 1138.05061
[25] Fiala, J.; Maxová, J., Cantor – bernstein type theorem for locally constrained graph homomorphisms, European journal of combinatorics, 7, 27, 1111-1116, (2006) · Zbl 1107.05066
[26] Fiala, J.; Paulusma, D., A complete complexity classification of the role assignment problem, Theoretical computer science, 1, 349, 67-81, (2005) · Zbl 1124.91055
[27] Graph-theoretic concepts in computer science, (), Revised Papers (2006)
[28] Gardiner, A., Antipodal covering graphs, Journal of combinatorial theory B, 16, 255-273, (1974) · Zbl 0267.05111
[29] Godsil, C.; Royle, G., ()
[30] Griggs, J.R.; Yeh, R.K., Labelling graphs with a condition at distance 2, SIAM journal on discrete mathematics, 5, 4, 586-595, (1992) · Zbl 0767.05080
[31] Gross, J.L.; Tucker, T.W., Generating all graph coverings by permutation voltage assignments, Discrete mathematics, 18, 273-283, (1977) · Zbl 0375.55001
[32] Grothendieck, A., Technique de descente et théorèmes d’existence en géométrie algébrique. I: Généralités. descente par morphismes fidèlement plats, Séminaire bourbaki, 12, 190, (1959/60), 1960
[33] Hell, P.; Nešetřil, J., Graphs and homomorphisms, (2004), Oxford University Press · Zbl 1062.05139
[34] Hliněný, P., \(K_{4, 4} - e\) has no finite planar cover, Journal of graph theory, 21, 1, 51-60, (1998) · Zbl 0892.05039
[35] Hliněný, P.; Thomas, R., On possible counterexamples to negami’s planar cover conjecture, Journal of graph theory, 46, 3, 183-206, (2004) · Zbl 1049.05028
[36] Hopcroft, J., An \(n \log n\) algorithm for minimizing states in a finite automaton, (), 189-196 · Zbl 0293.94022
[37] Kratochvíl, J.; Proskurowski, A.; Telle, J.A., Covering directed multigraphs I. colored directed multigraphs, (), 242-257 · Zbl 0890.68095
[38] J. Kratochvíl, A. Proskurowski, J.A. Telle, Covering directed multigraphs II. when 2-SAT helps. Tech. Rep. 1997-354, KAM-DIMATIA Preprint Series, 1997
[39] Kratochvíl, J.; Proskurowski, A.; Telle, J.A., Covering regular graphs, Journal of combinatorial theory, series B, 71, 1, 1-16, (1997) · Zbl 0895.05049
[40] Kratochvíl, J.; Proskurowski, A.; Telle, J.A., Complexity of graph covering problems, Nordic journal of computing, 5, 173-195, (1998) · Zbl 0911.68076
[41] Kristiansen, P.; Telle, J.A., Generalized \(H\)-coloring of graphs, (), 456-466 · Zbl 1044.68129
[42] Leese, R.A.; Noble, S.D., Cyclic labellings with constraints at two distances, Electronic journal of combinatorics, 11, 1, (2004) · Zbl 1053.05111
[43] Leighton, F.T., Finite common coverings of graphs, Journal of combinatorial theory B, 33, 231-238, (1982) · Zbl 0488.05033
[44] Lerner, J., Role assignments, (), 216-252 · Zbl 1118.68336
[45] Litovsky, I.; Métivier, Y.; Zielonka, W., The power and the limitations of local computations on graphs, (), 333-345 · Zbl 0791.68131
[46] Liu, D.D.-F.; Zhu, X., Circulant distant two labeling and circular chromatic number, Ars combinatoria, 69, 177-183, (2003) · Zbl 1072.05570
[47] Lovász, L., Combinatorial problems and exercises, (1979), Akadémiai Kiadó Budapest · Zbl 0439.05001
[48] B.D. McKay, Nauty (No AUTomorphisms, Yes?). http://cs.anu.edu.au/ bdm/nauty/
[49] B.D. McKay, Backtrack programming and the graph isomorphism problem. Master’s thesis, University of Melbourne, 1974
[50] McKay, B.D., Practical graph isomorphism, Congressus numerantium, 30, 45-87, (1981)
[51] Mohar, B., A common cover of graphs and 2-cell embeddings, Journal of combinatorial theory, series B, 40, 94-106, (1986) · Zbl 0563.05022
[52] Mohar, B.; Thomassen, C., Graphs on surfaces, (2001), Johns Hopkins University Press Baltimore · Zbl 0979.05002
[53] Negami, S., Graphs which have no planar covering, Bulletin of the institute of mathematics, academia sinica, 4, 377-384, (1988) · Zbl 0676.05039
[54] Nešetřil, J., Homomorphisms of derivative graphs, Discrete mathematics, 1, 3, 257-268, (1971) · Zbl 0227.05109
[55] Petersen, J., Die theorie der regulären graphs, Acta Mathematica, XV, 193-220, (1891) · JFM 23.0115.03
[56] Reidemeister, K., Einführung in die kombinatorische topologie, (1932), Braunschweig: Friedr, Vieweg & Sohn A.-G. XII, 209 S · JFM 58.0611.01
[57] Robertson, N.; Seymour, P.D., Graph minors XX. wagner’s conjecture, Journal of combinatorial theory series B, 92, 2, 325-357, (2004) · Zbl 1061.05088
[58] Sachs, H., Simultane überlagerung gegebener graphen, Publication of the mathematical institute of the Hungarian Academy of sciences, series A, 9, 415-427, (1964) · Zbl 0134.43401
[59] Stallings, J.R., Topology of finite graphs, Inventiones mathematicae, 71, 551-566, (1983) · Zbl 0521.20013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.