Harmonious coloring

Harmonious coloring of 7-tree with 3 levels using 12 colors. The harmonius chromatic number of this graph is 12 since the vertices are 57, and the color's pair are ncolor*(ncolor-1)/2 >= 57 iff ncolor>=12. Moreover (3/2)*(7+1)=12(see Mitchem's Formula).

In graph theory, a harmonious coloring is a (proper) vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number χ_H("G") of a graph "G" is the minimum number of colors needed for any harmonious coloring of "G".

Every graph has a harmonious coloring, since it suffices to assign every vertex a distinct color; thus χ_H("G") ≤ |V(G)|. There trivially exist graphs "G" with χ_H("G") > χ("G") (where χ is the chromatic number); one example is the path of length 2, which can be 2-colored but has no harmonious coloring with 2 colors.

Some properties of χ_H("G"):
# χ_H(T_"k",3) = &lceil;(3/2)("k"+1)&rceil;, where T_"k",3 is the complete "k"-ary tree with 3 levels. (Mitchem 1989)

Harmonious coloring was first proposed by Frank, Harary and Plantholt (1982).Still very little is known about it.

Look at other dictionaries:

coloring — Synonyms and related words: Klangfarbe, abstractionism, achromatism, acrylic painting, acting, affectation, affective meaning, appearance, attitudinizing, bearing, bloom, bluff, bluffing, blush, blushing, cast, cheating, chromatic, chromatism,… … Moby Thesaurus
harmonious — Synonyms and related words: accompanying, accordant, according, affable, affirmative, agreeable, agreeing, akin, amiable, amicable, anal, answerable, arranged, associate, associated, assonant, assonantal, at one, at one with, attuned, balanced,… … Moby Thesaurus
Complete coloring — of the Clebsch graph with 8 colors. Every pair of colors appears on at least one edge. No complete coloring with more colors exists: in any 9 coloring some color would appear only at one vertex, and there would not be enough neighboring vertices… … Wikipedia
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. 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… … Wikipedia
Exact coloring — The n coloring of Complete graph K n is an exact coloring.In graph theory, an exact coloring is a (proper) vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices. In essence, an exact coloring is a coloring … Wikipedia
List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 … Wikipedia
George Morland — (1763 1804) was an English painter of animals and rustic scenes. LifeMorland was born in London on 26 June 1763. His mother was a Frenchwoman, who possessed a small independent property of her own. His grandfather, George H. Morland, was a… … Wikipedia
Titian — Tiziano redirects here. For other uses, see Tiziano (disambiguation). For other uses, see Titian (disambiguation). Titian Titian self portrait, c.1567; Museo del Prado, Madrid Birth name … Wikipedia
List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… … Wikipedia
Color analysis (art) — Color analysis, also called skin tone color matching or color seasons, is the process of finding colors of clothing and makeup to match a person s complexion, eye color, and hair color. It is often used as an aid to wardrobe planning and style… … Wikipedia

Academic Dictionaries and Encyclopedias

Harmonious coloring

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Harmonious coloring

Look at other dictionaries:

Share the article and excerpts

Direct link