Contents

-

Graph Partitions

T. D. Porter1
1SOUTHERN ILLINOIS UNIVERSITY CARBONDALE, ILLINOIS 62901

Abstract

For any graph G, and all s=2k, we show there is a partition of the vertex set of G into s sets U1,,Us, so that both:
e(G[Ui])e(G)s2+e(G)s,for i=1,,s and i=1se(G[Ui])e(G)s.