Stiefel-Whitney test graph

Furthermore, T is called a Stiefel—Whitney test graph if it is a Stiefel Whitney n-test graph for every integer n > x(T). 

Corollary 19.4. Assume that T is a Stiefel-Whitney test graph. Then for... 

This property can be taken as a blueprint for the homotopy version of Stiefel-Whitney test graphs. 

Note that by Corollary 8.26, we have h(X) > connX + 1 for an arbitrary Z2-space X. Therefore, comparing equations (19.2) and (19.1), we see that if a graph T is a Stiefel-Whitney test graph, then, it is also a homotopy test graph. 

Let us stress again that in analogy to the fact that the height is defined for Z2-spaces, the term Stiefel-Whitney test graph actually refers to a pair (T, 7), where T is a graph and 7 is an involution of T that flips an edge. The following question arises naturally in this context. 

Proposition 19.6. Let T he an arbitrary graph, and let A and B be Stiefel-Whitney test graphs such that x T) = x( ) = x B)- Assume further that there exist L2-equivariant graph hornornorphisms ip A T and if T B. Then T is also a Stiefel-Whitney test graph. 

Stiefel-Whitney Characteristic Classes and Test Graphs.327... 

It is then a positive surprise that the tests based on the Stiefel-Whitney characteristic classes are pol3momially computable if we fix the test graph and the tested dimension and consider the computational complexity with respect to the number of vertices. 

The following theorem describes the standard way to use the nonnullity of the powers of Stiefel-Whitney characteristic classes associated to Z2-spaces as tests for graph colorings. 

Definition 19.3. Let T be a graph with a Z2-action that flips an edge. Then T is called a Stiefel—Whitney n-test graph if we have... 

---