International Journal of Mathematics and Mathematical Sciences
Volume 17 (1994), Issue 4, Pages 697-702

Zero-sum partition theorems for graphs

Y. Caro,1 I. Krasikov,2,3 and Y. Roditty2,3

1Department of Mathematics, Haifa University, Oranim, Israel
2School of Mathematics, Tel-Aviv University, Ramat Aviv, Israel
3Department of Mathematics, Beit-Berl College, Kfar-Saba, Israel

Received 13 November 1992; Revised 2 February 1993

Copyright © 1994 Y. Caro et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Let q=pn be a power of an odd prime p. We show that the vertices of every graph G can be partitioned into t(q) classes V(G)=t=1t(q)Vi such that the number of edges in any induced subgraph Vi is divisible by q, where t(q)32(q1)(2(q1)1)124+98, and if q=2n, then t(q)=2q1.

In particular, it is shown that t(3)=3 and 4t(5)5.