New upper bounds on harmonious colorings
Keith J. Edwards, Colin McDiarmid · Journal of Graph Theory · 1994
Abstract We present an improved upper bound on the harmonious chromatic number of an arbitrary graph. We also consider „fragmentable”︁ classes of graphs (an example is the class of planar graphs) that are, roughly speaking, graphs that can be decomposed into bounded‐sized components by removing a small proportion of the vertices. We show that for such graphs of bounded degree the harmonious chromatic number is close to the lower bound (2m)1/2, where m is the number of edges.