Homomorphisms of Edge-coloured Graphs and Coxeter Groups

N. Alon and T. H. Marshall


Let $G_1=(V_1, E_1)$ and $G_2 = (V_2, E_2)$ be two edge-coloured
graphs (without multiple edges or loops). A {em homomorphism} is a
mapping $phi: V_1 longmapsto 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 colour of the edge
$phi(u)phi(v)$ is the same as that of the edge $uv$.

We prove a number of results asserting the existence of a graph $G$,
edge-coloured from a set $C$, into which every member from a given
class of graphs, also edge-coloured from $C$, maps homomorphically.

We apply one of these results to prove that every 3-dimensional hyperbolic
reflection group, having rotations of orders from the set $M={m_1,
m_2, ldots m_k }$, has a torsion-free subgroup of index not
exceeding some bound, which depends only on the set $M$.


Math Review Classification
Primary 05C15, 05C25, 20F55, 51F15

Last Updated

9 pages

This article is available in: