An algebraic characterization of k--colorability

Delaram Kahrobaei, Thomas Koberda, Ramón Flores

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Number of pages6
JournalProceedings of the American Mathematical Society
Publication statusAccepted/In press - 2020

Bibliographical note

© Copyright 2020, American Mathematical Society. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

Cite this