Homomorphisms of Edge-Colored Graphs and Coxeter Groups

N. Alon, T. H. Marshall

Research output: Contribution to journalArticlepeer-review

59 Scopus citations


Let G1 = (V1, E1) and G2 = (V2, E2) be two edge-colored graphs (without multiple edges or loops). A homomorphism is a mapping φ : V1 → V2 for which, for every pair of adjacent vertices u and v of G1, φ (u) and φ (v) are adjacent in G2 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. We apply one of these results to prove that every three-dimensional hyperbolic reflection group, having rotations of orders from the set M = {m1, m2, . . . , mk], has a torsion-free subgroup of index not exceeding some bound, which depends only on the set M.

Original languageEnglish (US)
Pages (from-to)5-13
Number of pages9
JournalJournal of Algebraic Combinatorics
Issue number1
StatePublished - 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Discrete Mathematics and Combinatorics


  • Coxeter group
  • Graph
  • Homomorphism
  • Reflection group


Dive into the research topics of 'Homomorphisms of Edge-Colored Graphs and Coxeter Groups'. Together they form a unique fingerprint.

Cite this