An algebraic characterization of k--colorability

Delaram Kahrobaei; Thomas Koberda; Ramón Flores

An algebraic characterization of k--colorability

Delaram Kahrobaei, Thomas Koberda, Ramón Flores

Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Number of pages	6
Journal	Proceedings of the American Mathematical Society
Publication status	Accepted/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.

Access to Document

raag-coloring270920
© 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.
Accepted author manuscript, 249 KB

https://arxiv.org/abs/2003.01484

Cite this

@article{7960fe8679064574ad603cbbc39ef312,

title = "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.",

author = "Delaram Kahrobaei and Thomas Koberda and Ram{\'o}n Flores",

note = "{\textcopyright} Copyright 2020, American Mathematical Society. This is an author-produced version of the published paper. Uploaded in accordance with the publisher{\textquoteright}s self-archiving policy. Further copying may not be permitted; contact the publisher for details.",

year = "2020",

language = "English",

journal = "Proceedings of the American Mathematical Society",

issn = "1088-6826",

publisher = "American Mathematical Society",

}

TY - JOUR

T1 - An algebraic characterization of k--colorability

AU - Kahrobaei, Delaram

AU - Koberda, Thomas

AU - Flores, Ramón

N1 - © 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.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

M3 - Article

SN - 1088-6826

JO - Proceedings of the American Mathematical Society

JF - Proceedings of the American Mathematical Society

ER -