An upper bound for the harmonious chromatic number of a graph

✍ Scribed by Sin-Min Lee; John Mitchem

• Publisher: John Wiley and Sons
• Year: 1987
• Tongue: English
• Weight: 149 KB
• Volume: 11
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190110414

✦ Synopsis

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 over 100 years. Recently [l-41, vertex colorings that required each edge have a different incident color pair have been considered. Frank, Harary, and Plantholt [ 11, wrote the first paper on the subject, which was mentioned to one of them by Pierre Duchet.

Following that paper we make the following definition:

A line-distinguishing k-coloring of G is a k-coloring such that for any two distinct lines e , and e2, f i e , ) # f ( e z ) . The linedistinguishing chromatic number, h ( G ) , is the minimum k such that G has a line-distinguishing k-coloring.

Independently, but slightly later, Hopcroft and Krisnamoorthy [ 31 showed that determination of h(G) is an NP-complete problem. However, they used the term harmonious coloring number for X(G). In [4] Miller and Pritikin added one more condition to these colorings, namely that adjacent vertices receive distinct colors. In this paper, we follow Miller and Pritikin's definition. Specifically, a harmonious k-coloring of graph G is a k-coloring with adjacent vertices receiving different colors and all edges receiving different color pairs. The har- monious chromatic number of G , denoted h(G), is the minimum k for which G has a harmonious k-coloring.