By the same authors

From the same journal

An algebraic characterization of k--colorability

Research output: Contribution to journalArticlepeer-review

Full text download(s)




Publication details

JournalProceedings of the American Mathematical Society
DateAccepted/In press - 2020
Number of pages6
Original languageEnglish


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.

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.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations