An algebraic characterization of k--colorability.

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. [ABSTRACT FROM AUTHOR]