Vertex colouring edge partitions (Q2485946): Difference between revisions

Suppose that the edges of a graph are assigned labels from a \(k\)-set, or equivilently, the edges are partitioned into \(k\) parts. Each vertex \(v\) has an associated multiset \(X_v\) consisting of the labels on its incident edges. The partition is a (proper) vertex coloring if for every edge \(uv\), \(X_u \neq X_v\). The authors show that the edges of any graph (except those containing a component isomorphic to \(K_2\)) have a partition into four parts such that the associated multisets form a vertex coloring. Moreover, if the minimum degree is at least 1000, then the edges can be partitioned into three parts yielding a vertex coloring. This paper is well written and the result is interesting.