The Harmonious Chromatic Number of Bounded Degree Graphs

Abstract

A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring. Let d be a fixed positive integer, and ε>0. We show that there is a natural number M such that if G is any graph with m⩾M edges and maximum degree at most d, then the harmonious chromatic number h(G) satisfies ( 2 m ) 1 / 2 ⩽ h ( G ) ⩽ ( 1 + ε ) ( 2 m ) 1 / 2 .