Premium
The Harmonious Chromatic Number of Bounded Degree Graphs
Author(s) -
Edwards Keith
Publication year - 1997
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610797004857
Subject(s) - combinatorics , chromatic scale , mathematics , bounded function , vertex (graph theory) , graph , degree (music) , simple graph , windmill graph , integer (computer science) , brooks' theorem , discrete mathematics , computer science , 1 planar graph , physics , chordal graph , graph power , line graph , mathematical analysis , acoustics , programming language
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.