Homomorphisms of Edge-Colored Graphs and Coxeter Groups
N. Alon
and T.H. Marshall2
2t
DOI: 10.1023/A:1008647514949
Abstract
Let G 1 = ( V 1 , E 1 )\text and G 2 = ( V 2 , E 2 ) 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 \textregistered V 2 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.
( 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 graph G , edge-colored from a set C, into which every member from a given class of graphs, also edge-colored from C, maps homomorphically.
Pages: 5–13
Keywords: graph; homomorphism; Coxeter group; reflection group
Full Text: PDF
References
1. N. Alon, B. Mohar, and D.P. Sanders, “Acyclic colourings of graphs on surfaces,” Israel J. Math., to appear.
2. O.V. Borodin, “On acyclic colorings of planar graphs,” Discrete Math. 25 (1979), 211-236.
3. 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.
4. 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.
5. K.N. Jones and A.W. Reid, “Minimal index torsion-free subgroups of Kleinian groups,” preprint.
6. B. Maskit, Kleinian Groups, Springer-Verlag,
1987. P1: SMAP1: SMA Journal of Algebraic Combinatorics KL583-01-ALO May 18, 1998 13:58 HOMOMORPHISMS OF EDGE-COLORED GRAPHS AND COXETER GROUPS 13
7. J. Neśetŕil, A. Raspaud, and E. Sopena, “Colorings and girth of oriented planar graphs,” preprint, 1995.
8. A. Raspaud and E. Sopena, “Good and semi-strong colorings of oriented planar graphs,” Inform. Proc. Letters 51 (1994), 171-174.
9. A. Selberg, On Discontinuous Groups in Higher-dimensional Spaces, Tata Institute, Bombay, 1960.
10. D. Singerman, “Subgroups of Fuchsian groups and finite permutation groups,” Bull. London Math. Soc. 2 (1970), 319-323.
11. E. Sopena, “The chromatic number of oriented graphs,” preprint, 1995.
12. A.Yu. Vesnin, “Three-dimensional hyperbolic manifolds of the L\ddot obell type,” Siberian Math. J. 28 (1987), 731-734.
13. E.B. Vinberg (Ed.), Geometry II, Encyclopaedia of Mathematical Sciences, Vol. 29, Springer-Verlag, 1993.
2. O.V. Borodin, “On acyclic colorings of planar graphs,” Discrete Math. 25 (1979), 211-236.
3. 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.
4. 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.
5. K.N. Jones and A.W. Reid, “Minimal index torsion-free subgroups of Kleinian groups,” preprint.
6. B. Maskit, Kleinian Groups, Springer-Verlag,
1987. P1: SMAP1: SMA Journal of Algebraic Combinatorics KL583-01-ALO May 18, 1998 13:58 HOMOMORPHISMS OF EDGE-COLORED GRAPHS AND COXETER GROUPS 13
7. J. Neśetŕil, A. Raspaud, and E. Sopena, “Colorings and girth of oriented planar graphs,” preprint, 1995.
8. A. Raspaud and E. Sopena, “Good and semi-strong colorings of oriented planar graphs,” Inform. Proc. Letters 51 (1994), 171-174.
9. A. Selberg, On Discontinuous Groups in Higher-dimensional Spaces, Tata Institute, Bombay, 1960.
10. D. Singerman, “Subgroups of Fuchsian groups and finite permutation groups,” Bull. London Math. Soc. 2 (1970), 319-323.
11. E. Sopena, “The chromatic number of oriented graphs,” preprint, 1995.
12. A.Yu. Vesnin, “Three-dimensional hyperbolic manifolds of the L\ddot obell type,” Siberian Math. J. 28 (1987), 731-734.
13. E.B. Vinberg (Ed.), Geometry II, Encyclopaedia of Mathematical Sciences, Vol. 29, Springer-Verlag, 1993.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition