In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a harmonious coloring is a (proper)
vertex coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
in which every pair of colors appears on ''at most'' one pair of adjacent
vertices. It is the opposite of the
complete coloring
In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on ''at least'' one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper ...
, which instead requires every color pairing to occur ''at least'' once. The harmonious chromatic number of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
is the minimum number of colors needed for any harmonious coloring of .
Every graph has a harmonious coloring, since it suffices to assign every vertex a distinct color; thus . There trivially exist graphs with (where is the
chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
); one example is any path of , which can be 2-colored but has no harmonious coloring with 2 colors.
Some properties of :
:
where is the complete
-ary tree with 3 levels. (Mitchem 1989)
Harmonious coloring was first proposed by Harary and Plantholt (1982). Still very little is known about it.
See also
*
Complete coloring
In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on ''at least'' one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper ...
*
Harmonious labeling
External links
''A Bibliography of Harmonious Colourings and Achromatic Number''by Keith Edwards
References
*
* Jensen, Tommy R.; Toft, Bjarne (1995). ''Graph coloring problems''. New York: Wiley-Interscience. .
* {{cite journal , doi = 10.1016/0012-365X(89)90207-0 , last1 = Mitchem , first1 = J. , year = 1989 , title = On the harmonious chromatic number of a graph , journal = Discrete Math. , volume = 74 , issue = 1–2 , pages = 151–157 , doi-access = free
Graph coloring