Graphs with Small Upper Line-Distinguishing and Upper Harmonious Chromatic Numbers

Abstract

A $k$-line-distinguishing coloring of a graph $G=(V,E)$ is a partition of $V$ into $k$ sets $V_1,\dots ,V_k$ such that $q(⟨V_i⟩)\le 1$ for $i=1,\dots ,k$ and $q(V_i,V_j)\le 1$ for $1\le i\le j\le 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^{\prime }(G)$, is defined as the maximum cardinality of a minimal line-distinguishing coloring of a graph $G$. For any graph $G$ of maximum degree $\mathrm{\Delta }(G)$, $H^{\prime }(G)\ge \mathrm{\Delta }(G)$ and $H(G)\ge \mathrm{\Delta }(G)+1$.

We characterize connected graphs $G$ that contain neither a triangle nor a 5-cycle for which $H(G)=\mathrm{\Delta }(G)+1$. We show that a triangle-free connected graph $G$ satisfies $H^{\prime }(G)=\mathrm{\Delta }(G)$ if and only if $G$ is a star $K_{1,\mathrm{\Delta }(G)}$. A partial characterization of connected graphs $G$ for which $H^{\prime }(G)=\mathrm{\Delta }(G)$ is obtained.