No label defined (Q4027170)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 125470
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 125470 |
Statements
21 February 1993
0 references
harmonious \(k\)-coloring
0 references
harmonious chromatic number
0 references
Nordhaus-Gaddum theorem
0 references
bounds
0 references
0.8880952596664429
0 references
0.888075590133667
0 references
0.8870849609375
0 references
0.8659855127334595
0 references
[For the entire collection see Zbl 0748.00023.] A harmonious \(k\)-coloring of a graph \(G\) is a proper \(k\)-coloring (adjacent vertices colored differently) such that no two edges have the same pair of colors on their incident vertices. The harmonious chromatic number \(h(G)\) is the minimum \(k\) for which \(G\) has a harmonious \(k\)- coloring. Among the results obtained in this paper is the analog of the Nordhaus-Gaddum theorem for chromatic number [Amer. Math. Mon. 63, 175- 177 (1956; Zbl 0070.185)], the analog being: For \(G\) a graph of order \(n\), \(n+1\leq h(G)+h(\overline G)\leq 2n\); \(n\leq h(G)\cdot h(\overline G)\leq n^ 2\); for \(n\geq 4\), all bounds are sharp.
0 references
