Abstract
We show that the vertex coloring problem for finite simplicial complexes can be translated into the algebraic homotopy problem of ellipticity for rational spaces. We follow the ideas of Lechuga–Murillo for the classical vertex coloring of graphs.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Dobrinskaya, N., Møller, J., Notbohm, D.: Vertex colorings of simplicial complexes (preprint). arXiv:1007.0710v1
Félix, Y., Halperin, S., Thomas, J.C.: Rational Homotopy Theory, Graduate Texts in Mathematics, vol. 205, 4th edn. Springer, Berlin (2001)
Halperin, S.: Torsion gaps in the homotopy of finite complexes. II. Topology 30(3), 471–478 (1991)
Lechuga, L., Murillo, A.: Complexity in rational homotopy. Topology 39(1), 89–94 (2000)
Lechuga, L., Murillo, A.: The fundamental class of a rational space, the graph coloring problem and other classical decision problems. Bull. Belg. Math. Soc. Simon Stevin 8(3), 451–467 (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
First author is partially supported by Grant MTM2013-43687-P (European FEDER support included). Second author is partially supported by Grant MTM2013-41768-P (European FEDER support included), and JA Grant FQM-213. Both authors are partially supported by Xunta de Galicia Grant EM2013/016.
Rights and permissions
About this article
Cite this article
Costoya, C., Viruel, A. Rational homotopy theory for computing colorability of simplicial complexes. AAECC 26, 207–212 (2015). https://doi.org/10.1007/s00200-014-0249-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00200-014-0249-9