scientific article; zbMATH DE number 125470

Publication date 21 February 1993

bounds harmonious \(k\)-coloring harmonious chromatic number Nordhaus-Gaddum theorem

Coloring of graphs and hypergraphs (05C15)

[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.

Recommendations

Cited in

(22)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027170)