Zero-sum partition theorems for graphs. (1994) - Caro, Y.; Krasikov, I.; Roditty, Y.
Abstract : Letq = p n be a power of an odd primep . We show that the vertices of every graphG can be partitioned intot ( q ) classesV ( G ) = ⋃ t = 1 t ( q ) V i such that the number of edges in any induced subgraph〈 V i 〉 is divisible byq, wheret ( q ) ≤ 3 2 ( q − 1 ) − ( 2 ( q − 1 ) − 1 ) 1 2 4 + 9 8, and ifq = 2 n, thent ( q ) = 2 q − 1 . In particular, it is shown thatt ( 3 ) = 3 and4 ≤ t ( 5 ) ≤ 5 .