Top

Applicable Algebra in Engineering, Communication and Computing

Published in:

01-03-2015 | Original Paper

Rational homotopy theory for computing colorability of simplicial complexes

Authors: Cristina Costoya, Antonio Viruel

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 1-2/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article On higher dimensional cocyclic Hadamard matrices

next article Topology of acyclic complexes of tournaments and coloring

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

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)CrossRefMATHMathSciNet

Lechuga, L., Murillo, A.: Complexity in rational homotopy. Topology 39(1), 89–94 (2000)CrossRefMATHMathSciNet

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)MATHMathSciNet

Title: Rational homotopy theory for computing colorability of simplicial complexes
Authors: Cristina Costoya
Antonio Viruel
Publication date: 01-03-2015
Publisher: Springer Berlin Heidelberg
Published in: Applicable Algebra in Engineering, Communication and Computing / Issue 1-2/2015
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-014-0249-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1-2/2015

The third homotopy group as a $$\pi _1$$ π 1 -module

The trace space of the $$k$$ k -skeleton of the $$n$$ n -cube

On higher dimensional cocyclic Hadamard matrices

Computing fundamental groups from point clouds

Topology of acyclic complexes of tournaments and coloring

Membrane parallelism for discrete Morse theory applied to digital images

Premium Partner