This paper relates two properties of graphs—detachment and harmonious chromatic number—and obtains many new and interesting results. A detachment of a graph is obtained by splitting each vertex into one or more subvertices and having incident edges shared arbitrarily among the subvertices. A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least number of colors for such a coloring.
Edwards studies whether an arbitrary graph, H, is the detachment of some complete graph Kn. This paper proves for sufficiently large n (a very large value) that every cubic (every vertex has degree 3), planar triangle-free graph of n*(3n-1) vertices is a detachment of K{3n+1}. For some classes of graphs, this paper provides a polynomial time algorithm to test whether vertices can be partitioned as n to r classes, such that the degree in each vertex class is r. Finally, the author determines the exact values of harmonious chromatic numbers for many classes of graphs (with bounded degree). This paper is very well written.
