Premium
New upper bounds on harmonious colorings
Author(s) -
Edwards Keith,
McDiarmid Colin
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180305
Subject(s) - combinatorics , mathematics , bounded function , chromatic scale , upper and lower bounds , planar graph , graph , discrete mathematics , degree (music) , class (philosophy) , computer science , physics , mathematical analysis , artificial intelligence , acoustics
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 (2 m ) 1/2 , where m is the number of edges.