An algebraic characterization of $k$--colorability

Abstract

We characterize $k$--colorability of a simplicial graph via the intrinsic algebraic structure of the associated right-angled Artin group. As a consequence, we show that a certain problem about the existence of homomorphisms from right-angled Artin groups to products of free groups is NP--complete.

7 pages, to appear in Proc. Amer. Math. Soc

References in corpus (2)

• Embedability between right-angled Artin groups
• On rigidity and the isomorphism problem for tree braid groups