Homomorphisms of edge-colored graphs and Coxeter groups (Q1272907)

A homomorphism \(\phi:G_1\to G_2\) of edge-colored graphs is a map of vertices such that if \(u\) and \(v\) are joined by an edge of \(G_1\), then \(\phi(u)\) and \(\phi(v)\) are joined by an edge of \(G_2\) with the same color (in particular, \(\phi(u)\neq \phi(v)\)). For a given class \(\mathcal G\) of \(n\)-edge-colored graphs, one may ask if there exists an \(n\)-edge-colored graph \(H\) such that each graph in \(\mathcal G\) has a homomorphism into \(H\), and if so, how many vertices \(H\) must have. The authors find a lower bound for this number in case \(\mathcal G\) is the class of planar graphs and an upper bound in case it is the class of graphs with acyclic chromatic number \(\leq k\). (The acyclic chromatic number of a graph is the smallest number of colors with which its vertices can be properly colored so that at least three colors occur on any cycle.) These results are then applied to the following question: given a finite polyhedron \(P\) in 3-dimensional hyperbolic space whose dihedral angles are submultiples of \(\pi\), the group \(G\) generated by reflections in the faces of \(P\) is a Coxeter group. The subgroup \(G^0\) of \(G\) generated by the products of pairs of generators is called a hyperbolic reflection group. The problem is to determine the smallest possible index \(m(G^0)\) of a torsion-free subgroup of \(G^0\). (\(m(G^0)\) is finite, by Selberg's lemma.) It is known that this number is a multiple of the \(\text{g.c.d. }\ell(G^0)\) of the orders of all finite subgroups of \(G^0\); the authors show that the ratio \(m(G^0)/\ell(G^0)\) is bounded above by a constant depending only on \(\ell(G^0)\). The proof uses the fact that one can naturally associate to the standard presentation of \(G\) a planar edge-colored graph.