The fundamental class of a rational space, the graph coloring problem and other classical decision problems
Luis Lechuga, Aniceto Murillo · Bulletin of the Belgian Mathematical Society - Simon Stevin · 2001
The problem of k-coloring a graph is equivalent to deciding whether a particular cohomology class of a certain rational space vanishes.Although this problem is NP-hard we are able to construct a fast (polynomial) algorithm to give a representative of this class.We also associate to other classical decision problems rational spaces so that the given problem has a solution if and only if the associated space is not elliptic.As these spaces have null Euler homotopy characteristic we easily characterize when the given problem has a solution in terms of commutative algebra.