An algebraic characterization of $k$–colorability
An algebraic characterization of $k$–colorability
复制标题
$k$–可着色性的代数表征
DOI：
10.1090/proc/15391
复制
发表时间：
2021
影响因子：
1
通讯作者：
Koberda, Thomas
中科院分区：
文献类型：
--
作者：
Flores, Ramón;Kahrobaei, Delaram;Koberda, Thomas
我们通过相关直角 Artin 群的内在代数结构来表征单纯图的可着色性。因此，我们证明了关于直角 Artin 群到自由群的乘积的同态存在性的某个问题是 NP 完全的。参考
We characterize–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. References