𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the harmonious chromatic number of a graph

✍ Scribed by John Mitchem

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
755 KB
Volume
74
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The harmonious chromatic number of a graph G, denoted by h(G), is the least number of colon which can be assigned to the vertices of G such that adjacent vertices are colored differently and any two distinct edges have different color pairs. This is a slight variation of a definition given independently by Hopcroft and Krishnamoorthy and by Frank, Harary, and Plantholt. D. Johnson has shown that determining h(G) is an NP-complete problem. In this paper we give various other theorems on harmonious chromatic number and discuss various open questions.

πŸ“œ SIMILAR VOLUMES

On an upper bound for the harmonious chr
On an upper bound for the harmonious chromatic number of a graph
✍ Zhikang Lu πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 125 KB πŸ‘ 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.

Bounds for the harmonious chromatic numb
Bounds for the harmonious chromatic number of a graph
✍ I. Krasikov; Y. Roditty πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 231 KB πŸ‘ 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph given by Zhikang Lu and by C. McDiarmid and Luo Xinhua, independently (__Journal of Graph Theory__, 1991, pp. 345–347 and 629–636) and the lower bound given by D. G. Beane, N. L. Biggs, and B. J. Wilson (__Journal of Graph T

An upper bound for the harmonious chroma
An upper bound for the harmonious chromatic number of a graph
✍ Sin-Min Lee; John Mitchem πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 149 KB πŸ‘ 2 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o

A bound on the chromatic number of a gra
A bound on the chromatic number of a graph
✍ Paul A. Catlin πŸ“‚ Article πŸ“… 1978 πŸ› Elsevier Science 🌐 English βš– 392 KB

We give an upper bound on the chromatic number of a graph in terms of its maximum degree and the size of the largest complete subgraph. Our result extends a theorem due to i3rook.s.

A new upper bound for the harmonious chr
A new upper bound for the harmonious chromatic number
✍ Edwards, Keith πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 200 KB πŸ‘ 2 views

A harmonious coloring of a simple graph G is a proper vertex coloring such that 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 obtain a new upper bound for the harmonious chromatic number of general