Vertex colouring edge partitions

A partition of the edges of a graph G into sets {S-1,...,S-k} defines a multiset X-nu for each vertex nu where the multiplicity of i in X-nu is the number of edges incident to v in Si. We show that the edges of every graph can be partitioned into 4 sets such that the resultant multisets give a vertex colouring of G. In other words, for every edge (u, nu) of G, X-u not equal X-nu. Furthermore, if G has minimum degree at least 1000, then there is a partition of E(G) into 3 sets such that the corresponding multisets yield a vertex colouring. (c) 2005 Elsevier Inc. All rights reserved.