Abstract
Let \(G_1 = (V_1 ,E_1 ){\text{ and }}G_2 = (V_2 ,E_2 )\) be two edge-colored graphs (without multiple edges or loops). A homomorphism is a mappingϕ : \(V_1 \mapsto V_2 \) for which, for every pair of adjacent vertices u and v of G 1, ϕ(u) and ϕ(v) are adjacent in G 2 and the color of the edge ϕ(u)ϕ(v) is the same as that of the edge uv.
We prove a number of results asserting the existence of a graphG , edge-colored from a set C, into which every member from a given class of graphs, also edge-colored from C, maps homomorphically.
We apply one of these results to prove that every three-dimensional hyperbolic reflection group, having rotations of orders from the setM ={m1, m2,..., mk}, has a torsion-free subgroup of index not exceeding some bound, which depends only on the setM .
Article PDF
Similar content being viewed by others
References
N. Alon, B. Mohar, and D.P. Sanders, “Acyclic colourings of graphs on surfaces,” Israel J. Math., to appear.
O.V. Borodin, “On acyclic colorings of planar graphs,” Discrete Math. 25 (1979), 211-236.
M.D.E. Conder and G.J. Martin, “Cusps, triangle groups and hyperbolic 3-folds,” J. Austral. Math. Soc. Ser. A 55 (1993), 149-182.
A.L. Edmonds, J.H. Ewing, and R.S. Kulkarni, “Torsion-free subgroups of Fuchsian groups and tesselations of surfaces,” Invent. Math. 69 (1982), 331-346.
K.N. Jones and A.W. Reid, “Minimal index torsion-free subgroups of Kleinian groups,” preprint.
B. Maskit, Kleinian Groups, Springer-Verlag, 1987.
J. Neśetŕil, A. Raspaud, and E. Sopena, “Colorings and girth of oriented planar graphs,” preprint, 1995.
A. Raspaud and E. Sopena, “Good and semi-strong colorings of oriented planar graphs,” Inform. Proc. Letters 51 (1994), 171-174.
A. Selberg, On Discontinuous Groups in Higher-dimensional Spaces, Tata Institute, Bombay, 1960.
D. Singerman, “Subgroups of Fuchsian groups and finite permutation groups,” Bull. London Math. Soc. 2 (1970), 319-323.
E. Sopena, “The chromatic number of oriented graphs,” preprint, 1995.
A.Yu. Vesnin, “Three-dimensional hyperbolic manifolds of the Löbell type,” Siberian Math. J. 28 (1987), 731-734.
E.B. Vinberg (Ed.), Geometry II, Encyclopaedia of Mathematical Sciences, Vol. 29, Springer-Verlag, 1993.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Alon, N., Marshall, T. Homomorphisms of Edge-Colored Graphs and Coxeter Groups. Journal of Algebraic Combinatorics 8, 5–13 (1998). https://doi.org/10.1023/A:1008647514949
Issue Date:
DOI: https://doi.org/10.1023/A:1008647514949