On the Upper Line-Distinguishing and Upper Harmonious Chromatic Numbers of a Graph

Abstract

We introduce and study two new parameters, namely the upper harmonious chromatic number, \(H(G)\), and the upper line-distinguishing chromatic number, \(H'(G)\), of a graph \(G\).
\(H(G)\) is defined as the maximum cardinality of a minimal harmonious coloring of a graph \(G\), while \(H'(G)\) is defined as the maximum cardinality of a minimal line-distinguishing coloring of a graph \(G\).
We show that the decision problems corresponding to the computation of the upper line-distinguishing and upper harmonious chromatic numbers are NP-complete for general graphs \(G\).
We then determine \(H'(P_n)\) and \(H(P_n)\).
Lastly, we show that \(H\) and \(H’\) are incomparable, even for trees.