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^{\prime }(G)$, of a graph $G$.
$H(G)$ is defined as the maximum cardinality of a minimal harmonious coloring of a graph $G$, while $H^{\prime }(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^{\prime }(P_n)$ and $H(P_n)$.
Lastly, we show that $H$ and $H^{\prime }$ are incomparable, even for trees.