An algebraic characterization of 𝑘–colorability

Flores, Ramón; Kahrobaei, Delaram; Koberda, Thomas

doi:10.1090/proc/15391

An algebraic characterization of $k$–colorability
HTML articles powered by AMS MathViewer

by Ramón Flores, Delaram Kahrobaei and Thomas Koberda PDF

Proc. Amer. Math. Soc. 149 (2021), 2249-2255 Request permission

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.

References

Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. MR 2500087, DOI 10.1017/CBO9780511804090
Noel Brady and John Meier, Connectivity at infinity for right angled Artin groups, Trans. Amer. Math. Soc. 353 (2001), no. 1, 117–132. MR 1675166, DOI 10.1090/S0002-9947-00-02506-X
Ruth Charney, An introduction to right-angled Artin groups, Geom. Dedicata 125 (2007), 141–158. MR 2322545, DOI 10.1007/s10711-007-9148-6
Carl Droms, Isomorphisms of graph groups, Proc. Amer. Math. Soc. 100 (1987), no. 3, 407–408. MR 891135, DOI 10.1090/S0002-9939-1987-0891135-1
Ramón Flores, Delaram Kahrobaei, and Thomas Koberda, Algorithmic problems in right-angled Artin groups: complexity and applications, J. Algebra 519 (2019), 111–129. MR 3874519, DOI 10.1016/j.jalgebra.2018.10.023
Ramón Flores, Delaram Kahrobaei, and Thomas Koberda, Expanders and right-angled Artin groups, preprint (2020).
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
Oded Goldreich, Silvio Micali, and Avi Wigderson, Proofs that yield nothing but their validity, or All languages in NP have zero-knowledge proof systems, J. Assoc. Comput. Mach. 38 (1991), no. 3, 691–729. MR 1125927, DOI 10.1145/116825.116852
M. Gromov, Hyperbolic groups, Essays in group theory, Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York, 1987, pp. 75–263. MR 919829, DOI 10.1007/978-1-4613-9586-7_{3}
Susan Hermiller and Zoran Šunić, Poly-free constructions for right-angled Artin groups, J. Group Theory 10 (2007), no. 1, 117–138. MR 2288463, DOI 10.1515/JGT.2007.010
Mark Kambites, On commuting elements and embeddings of graph groups and monoids, Proc. Edinb. Math. Soc. (2) 52 (2009), no. 1, 155–170. MR 2475886, DOI 10.1017/S0013091507000119
Sang-hyun Kim and Thomas Koberda, Embedability between right-angled Artin groups, Geom. Topol. 17 (2013), no. 1, 493–530. MR 3039768, DOI 10.2140/gt.2013.17.493
Sang-Hyun Kim and Thomas Koberda, Free products and the algebraic structure of diffeomorphism groups, J. Topol. 11 (2018), no. 4, 1054–1076. MR 3989437, DOI 10.1112/topo.12079
Thomas Koberda, Right-angled Artin groups and a generalized isomorphism problem for finitely generated subgroups of mapping class groups, Geom. Funct. Anal. 22 (2012), no. 6, 1541–1590. MR 3000498, DOI 10.1007/s00039-012-0198-z
Marvin L. Minsky, Computation: finite and infinite machines, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0356580
Lucas Sabalka, On rigidity and the isomorphism problem for tree braid groups, Groups Geom. Dyn. 3 (2009), no. 3, 469–523. MR 2516176, DOI 10.4171/GGD/67
Massimiliano Sala, Teo Mora, Ludovic Perret, Shojiro Sakata, and Carlo Traverso (eds.), Gröbner bases, coding, and cryptography, Springer-Verlag, Berlin, 2009. MR 2590633, DOI 10.1007/978-3-540-93806-4
Herman Servatius, Automorphisms of graph groups, J. Algebra 126 (1989), no. 1, 34–60. MR 1023285, DOI 10.1016/0021-8693(89)90319-0