Lovasz test

The original Lovasz test, which was based on computing the connectivity of a certain abstract simplicial complex associated to the graph in question, also has high computational complexity, since determining the triviality of the homotopy groups is an extremely hard problem, even in low dimensions. 

---