Let t(G, q) denote the smallest integer t such that the vertex set V o
f the graph G can be partitioned into t classes V(G) = U-i=1(t) V-i su
ch that the number of edges in the induced subgraph [V-i] for 1 less t
han or equal to i less than or equal to t, is divisible by q. Using an
algebraic theorem due to Baker and Schmidt we prove that if q is a pr
ime power then 1(G,q) can be computed and a corresponding partition ca
n be presented in a polynomial time.