Menu
A \( k \)-line-distinguishing coloring of a graph \( G = (V, E) \) is a partition of \( V \) into \( k \) sets \( V_1, \ldots, V_k \) such that \( q(\langle V_i \rangle) \leq 1 \) for \( i = 1, \ldots, k \) and \( q(V_i, V_j) \leq 1 \) for \( 1 \leq i \leq j \leq k \). If the color classes in a line-distinguishing coloring are also independent, then it is called a harmonious coloring. A coloring is minimal if, when two color classes are combined, we no longer have a coloring of the given type.
The upper harmonious chromatic number, \( H(G) \), is defined as the maximum cardinality of a minimal harmonious coloring of a graph \( G \), while the upper line-distinguishing chromatic number, \( H'(G) \), is defined as the maximum cardinality of a minimal line-distinguishing coloring of a graph \( G \). For any graph \( G \) of maximum degree \( \Delta(G) \), \( H'(G) \geq \Delta(G) \) and \( H(G) \geq \Delta(G) + 1 \).
We characterize connected graphs \( G \) that contain neither a triangle nor a 5-cycle for which \( H(G) = \Delta(G) + 1 \). We show that a triangle-free connected graph \( G \) satisfies \( H'(G) = \Delta(G) \) if and only if \( G \) is a star \( K_{1, \Delta(G)} \). A partial characterization of connected graphs \( G \) for which \( H'(G) = \Delta(G) \) is obtained.