On the harmonious chromatic number of a graph

DOI10.1016/0012-365X(89)90207-0MaRDI QIDQ1823253zbMATH OpenDBLPWikidataFDO

Authors John Mitchem

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(89)90207-0

zbMATH Keywords

harmonious chromatic numbervertex colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

The harmonious chromatic number h(G) of a graph G is the least number of colours which can be assigned to the vertices of G such that each vertex has exactly one colour, adjacent vertices have different colours, and the endpoints of any two distinct edges determine distinct colour pairs. Determining h(G) is an NP-complete problem. In this paper results on the harmonious chromatic number of trees are presented. The harmonious chromatic number of 2-regular graphs with at most 2 components is given. Further considerations concern the harmonious chromatic number of r- regular graphs with p vertices and of complete n-ary trees on 3 levels.

Recommendations

• scientific article; zbMATH DE number 125470
• The harmonious coloring number of a graph
• scientific article; zbMATH DE number 4114662
• Bounds for the harmonious chromatic number of a graph
• On the harmonic index and the chromatic number of a graph
• An upper bound for the harmonious chromatic number of a graph
• On the Harmonious Coloring of Graphs
• On the harmonious coloring of certain class of graphs
• The Harmonious Chromatic Number of Bounded Degree Graphs
• On the chromatic number of some Harary graphs

Cites work

• An upper bound for the harmonious chromatic number of a graph
• scientific article; zbMATH DE number 4114662 (Why is no real title available?)
• scientific article; zbMATH DE number 3795986 (Why is no real title available?)
• scientific article; zbMATH DE number 3218576 (Why is no real title available?)
• scientific article; zbMATH DE number 3238443 (Why is no real title available?)
• On the Harmonious Coloring of Graphs

Cited in

(23)

• The harmonious chromatic number of complete \(r\)-ary trees
• The exact value of the harmonious chromatic number of a complete binary tree
• Harmonious chromatic number of directed graphs
• On the harmonic index and the chromatic number of a graph
• scientific article; zbMATH DE number 4134074 (Why is no real title available?)
• On the Harmonious Coloring of Graphs
• On the chromatic number of some Harary graphs
• A new upper bound for the harmonious chromatic number
• The Harmonious Chromatic Number of Almost All Trees
• On the harmonious coloring of collections of graphs
• scientific article; zbMATH DE number 1416479 (Why is no real title available?)
• The edge-distinguishing chromatic number of petal graphs, chorded cycles, and spider graphs
• Harmonious colouring of cycles, regular graphs, star n-leaf, festoon trees and bigraphs
• scientific article; zbMATH DE number 2230305 (Why is no real title available?)
• An \(iP_2\) extended star graph and its harmonious chromatic number
• On the harmonious chromatic number of graphs
• The harmonious chromatic number of a complete binary and trinary tree
• The harmonious coloring game
• The asymptotic existence of BIBDs having a nesting
• A sharp upper bound for the harmonious total chromatic number of graphs and multigraphs
• Banff designs: difference methods for coloring incidence graphs
• Approximate and exact results for the harmonious chromatic number
• The harmonic index of a graph and its DP-chromatic number

This page was built for publication: On the harmonious chromatic number of a graph

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