The exact value of the harmonious chromatic number of a complete binary tree

DOI10.1016/S0012-365X(96)00272-5MaRDI QIDQ1366782zbMATH OpenFDO

Authors Zhikang Lu

Publication date 25 January 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(96)00272-5

zbMATH Keywords

complete binary treeharmonious chromatic number

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Review text

The problem of finding the harmonious chromatic number of a graph \(G\) is known to be NP-hard. The coloring of a graph is harmonious if any pair of colors is used at most once for coloring a pair of adjacent vertices. There is an obvious lower bound for the number \(h(G)\) of colors---the smallest integer \(k\) such that \({k\choose 2}\geq E(G)\). The paper proves that this bound is also the exact value of \(h(G)\) in the class of complete binary trees.

Recommendations

• The complexity of harmonious colouring for trees
• The harmonious chromatic number of a complete binary and trinary tree
• On the harmonious chromatic number of a graph
• scientific article; zbMATH DE number 4114662

Cites work

• An upper bound for the harmonious chromatic number of a graph
• scientific article; zbMATH DE number 3795986 (Why is no real title available?)
• On the harmonious chromatic number of a graph
• On the Harmonious Coloring of Graphs
• The growth rate of the harmonious chromatic number
• The harmonious chromatic number of a complete binary and trinary tree
• The harmonious coloring number of a graph

Cited in

(9)

• The harmonious chromatic number of complete \(r\)-ary trees
• The complexity of harmonious colouring for trees
• The harmonious coloring problem is NP-complete for interval and permutation graphs
• scientific article; zbMATH DE number 4134030 (Why is no real title available?)
• On the Harmonious Coloring of Graphs
• scientific article; zbMATH DE number 1159282 (Why is no real title available?)
• Exact values for theb-chromatic number of a power completek-ary tree
• The Harmonious Chromatic Number of Almost All Trees
• The harmonious chromatic number of a complete binary and trinary tree

This page was built for publication: The exact value of the harmonious chromatic number of a complete binary tree

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