Premium
Upper bounds for harmonious colorings
Author(s) -
McDiarmid Colin,
Xinhua Luo
Publication year - 1991
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.3190150606
Subject(s) - combinatorics , mathematics , edge coloring , upper and lower bounds , chromatic scale , complete coloring , fractional coloring , graph , simple graph , greedy coloring , brooks' theorem , enhanced data rates for gsm evolution , simple (philosophy) , list coloring , discrete mathematics , graph power , computer science , artificial intelligence , line graph , mathematical analysis , philosophy , epistemology
A harmonious coloring of a simple graph G is a coloring of the vertices such that adjacent vertices receive distinct colors and each pair of colors appears together on at most one edge. The harmonious chromatic number h ( G ) is the least number of colors in such a coloring. We improve an upper bound on h ( G ) due to Lee and Mitchem, and give upper bounds for related quantities.