Homomorphisms of edge-colored graphs and Coxeter groups

被引:55
作者
Alon, N
Marshall, TH
机构
[1] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel
[2] Univ Auckland, Sch Math & Informat Sci, Auckland 1, New Zealand
关键词
graph; homomorphism; Coxeter group; reflection group;
D O I
10.1023/A:1008647514949
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G(1) = (V-1, F-1) and G(2) = (V-2, E-2) be two edge-colored graphs (without multiple edges or loops). A homomorphism is a mapping phi : V-1 \--> V-2 for which, for every pair of adjacent vertices u and v of G(1), phi(u) and phi(v) are adjacent in G(2) and the color of the edge phi(u)phi(upsilon) is the same as that of the edge u upsilon. 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. We apply one of these results to prove that every three-dimensional hyperbolic reflection group, having rotations of orders from the set M = {m(1), m(2),..., m(k)}, has a torsion-free subgroup of index not exceeding some bound, which depends only on the set M.
引用
收藏
页码:5 / 13
页数:9
相关论文
共 6 条
  • [1] ACYCLIC COLORINGS OF PLANAR GRAPHS
    BORODIN, OV
    [J]. DISCRETE MATHEMATICS, 1979, 25 (03) : 211 - 236
  • [2] CUSPS, TRIANGLE GROUPS AND HYPERBOLIC 3-FOLDS
    CONDER, MDE
    MARTIN, GJ
    [J]. JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY SERIES A-PURE MATHEMATICS AND STATISTICS, 1993, 55 : 149 - 182
  • [3] EDMONDS AL, 1982, INVENT MATH, V69, P331, DOI 10.1007/BF01389358
  • [4] GOOD AND SEMI-STRONG COLORINGS OF ORIENTED PLANAR GRAPHS
    RASPAUD, A
    SOPENA, E
    [J]. INFORMATION PROCESSING LETTERS, 1994, 51 (04) : 171 - 174
  • [5] SINGERMAN D., 1970, Bull. Lond. Math. Soc, V2, P319, DOI DOI 10.1112/BLMS/2.3.319
  • [6] VESNIN AY, 1987, SIBERIAN MATH J+, V28, P731