PROBLEMS IN ZERO-SUM COMBINATORICS

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.