On the harmonious chromatic number of graphs

Suppose that $\epsilon$ identifies vertices $u$, $v$ with $d_{G}(u,v)\geq 3$, $h(\epsilon(G))=k$, and let $\varsigma^{\prime}$ be a harmonious $k$-coloring of $\epsilon(G)$. Consider a vertex $k$-coloring $\varsigma$ of $G$ determined by $\varsigma^{\prime}$ as follows:

Clearly, $\varsigma$ is harmonious, and so $h(G)\leq k=h(\epsilon(G))$. ∎

First, suppose that $h(\epsilon(G))=h(G)=k$, and let $\varsigma^{\prime}$ be a harmonious $k$-coloring of $\epsilon(G)$. Then the coloring $\varsigma$, which is determined by $\varsigma^{\prime}$ as in the proof of Proposition 1, is a harmonious $h(G)$-coloring of $G$ with $\varsigma(u)=\varsigma(v)$. Now, suppose that $\varsigma(u)=\varsigma(v)$ for a harmonious $h(G)$-coloring $\varsigma$ of $G$. Then the restriction of $\varsigma$ to $V(\epsilon(G))$ is a harmonious $h(G)$-coloring of $\varsigma(G)$. Thus $h(\varsigma(G))\leq h(G)$. By Proposition 1, $h(G)\leq h(\varsigma(G))$, and the result follows. ∎

By Proposition 1, $h(G)\leq h(\epsilon(G))$. Suppose that $h(G)=k$ and a harmonious $k$-coloring of $G$ is given with the colors $1,2,\dots,k$ and $\deg(u)=\min\{\deg(u),\deg(v)\}$ with $N(u)=\{u_{1},u_{2},\dots,u_{\deg(u)}\}$. Define a coloring $\varsigma^{\prime}$ of $\epsilon(G)$ by

Since $\varsigma^{\prime}$ is a harmonious coloring of $\epsilon(G)$ using at most $k+\deg(u)+1$ colors, the result follows. ∎

Clearly, $h(G)\leq h(G+uv)$. To prove the other inequality, consider a harmonious $h(G)$-coloring $\varsigma$ of $G$. If $\varsigma$ is a harmonious coloring of $G+uv$, then $h(G+uv)=h(G)$. Otherwise recoloring one of vertices $u$, $v$ with a new color yields a harmonious $(h(G)+1)$-coloring of $G+uv$. Indeed, if $\varsigma(u)=\varsigma(v)$, then recoloring $u$ does the job. On the other hand, under the assumption $\varsigma(u)\not=\varsigma(v)$ there is $w\in\{u,v\}$ such that with $\{w,x\}=\{u,v\}$ the vertex $w$ does not have in $G$ a neighbor colored with $\varsigma(x)$; in such a case recolor $w$. ∎

Let $G_{r}$ be the vertex-disjoint union of graphs $L=K_{1,r-1}$ and $R=K_{1,r-1}$ with $V(L)=\{u_{0},u_{1},\dots,u_{r-1}$ and $V(R)=\{v_{0},v_{1},\dots,v_{r-1}$, where $u_{0}$, $v_{0}$ are vertices of degree $r-1$. It is easy to see that $h(G_{r})=r+1$.

Now let $f$ be a harmonious homomorphism of the graph $G_{r}$, and let $\epsilon$ be the first elementary harmonious homomorphism applied when determining $f$. The homomorphism $\epsilon$ identifies vertices $u$, $v$ with $d_{G_{r}}(u,v)\geq 3$, say $u\in V(L)$ and $v\in V(R)$.

1. 1.

   If $u=u_{0}$ and $v=v_{0}$,then $\epsilon(G_{r})=f(G_{r})=K_{1,2r-2}$ and $h(f(G_{r}))=2r-1$.

2. 2.

   If $u=u_{0}$ and $v\not=v_{0}$, then without loss of generality we may suppose that $v=v_{r-1}$. Any other elementary harmonious homomorphism applied in the process of establishing $f$ has to identify a leaf of $L$ with a leaf $v_{j}$ of $R$, $j\not=r-1$. Without loss of generality let $u_{i}$ be identified with $v_{i}$ for $i\in\{1,2,\dots,r-2\}$. The resulting graph $f(G_{r})$ of diameter two has the leaf $u_{r-1}$, $r-2$ vertices $u_{i}$ of degree two, $i=\{1,2,\dots,r-2$, the vertex $u_{0}$ of degree $r$ and its neighbor $v_{0}$ of degree $r-1$; therefore, $h(f(G_{r}))=r+1$.

3. 3.

   If $u\not=u_{0}$ and $v=v_{0}$, we proceed similarly as in the case 2 to conclude that $h(f(G_{r}))=r+1$.

4. 4.

   If $u\not=u_{0}$ and $v\not=v_{0}$, then $d_{\epsilon(G_{r})}(u_{0},v_{0})=2$. Therefore, at most one of the vertices $u_{0}$, $v_{0}$ is involved in elementary harmonious homomorphisms leading to the resulting graph $H$ of diameter two. Consequently, $H$ is either (isomorphic to) the graph $f(G_{r})$ from the case $c\in\{2,3\}$ or equal to $K_{2,r-1}$, and so we have $h(H)=r+1$.

By inspection of the cases 1-4 we see that $ha(G_{r})=2r-1$. ∎

Suppose that the homomorphism $\epsilon$ identifies vertices $u,v\in V(G)$ (with $d_{G}(u,v)\geq 3$).

To prove that $h(\overline{G})-1\leq h(\overline{\epsilon(G)})$ let $h(\overline{\epsilon(G)})=k$, and let a coloring $\varsigma\colon V(\overline{\epsilon(G)})\rightarrow\{1,2,\dots,k\}$ be harmonious. Consider the proper vertex coloring $\varsigma^{\prime}\colon V(\overline{G})\rightarrow\{1,2,\dots,k+1\}$ defined by

Evidently, $\varsigma^{\prime}$ is harmonious. Therefore, $h(G)\leq k+1=h(\varsigma(G))+1$, and the required inequality follows.

Now, we show that $h(\overline{\epsilon(G)})\leq h(\overline{G})$. With $h(\overline{G})=l$ let $\mathcal{P}=\{V_{1},V_{2},\dots,V_{l}\}$ be the partition of $V(\overline{G})$ into (independent) color classes of a harmonious $l$-coloring of $\overline{G}$. Since $uv\not\in E(G)$, we have $uv\in E(\overline{G})$, and so without loss of generality we may suppose that $u\in V_{1}$ and $v\in V_{l}$. Let $V^{\prime}_{i}=V_{i}$ for $i\in\{1,2,\dots,l-1\}$, and $V^{\prime}_{l}=V_{l}\setminus\{v\}$. Further, let $p=l$ if $V^{\prime}_{l}\not=\emptyset$, and $p=l-1$ if $V^{\prime}_{l}=\emptyset$. Then $\mathcal{P}^{\prime}=\{V^{\prime}_{1},V^{\prime}_{2},\dots,V^{\prime}_{p}\}$ is a partition of $V(\overline{\epsilon(G)})$. The sets $V^{\prime}_{2},V^{\prime}_{3},\dots,V^{\prime}_{p}$ do not contain $u$, hence they are independent in $\overline{\epsilon(G)}$. The set $V^{\prime}_{1}$ is independent in $\overline{\epsilon(G)}$, too. First, distinct vertices of $V^{\prime}_{1}\setminus\{u\}$ are nonadjacent in $\overline{\epsilon(G)}$, since they are nonadjacent in $\overline{G}$. Next, if vertices $u$ and $w\in V^{\prime}_{1}\setminus\{u\}$ are adjacent in $\epsilon(G)$, they are nonadjacent in $\epsilon(G)$, which means that neither $uw$ nor $vw$ is an edge in $G$; therefore, vertices $u,w\in V_{1}$ are adjacent in $\overline{G}$, a contradiction. The partition $\mathcal{P}^{\prime}$ represents a harmonious coloring of $\overline{\epsilon(G)}$. Indeed, it suffices to prove that for any $i\in\{2,3,\dots,p\}$ there is at most one edge joining in $\overline{\epsilon(G)}$ a vertex of $V^{\prime}_{1}$ to a vertex of $V^{\prime}_{i}$. Assuming the opposite, there are vertices $w\in V^{\prime}_{1}\setminus\{u\}$ and $x,y\in V^{\prime}_{i}$, $x\not=y$, such that $ux,wy\in E(\overline{\epsilon(G)})$. Consequently, $\{ux,wy\}\cap E(\epsilon(G))=\emptyset$, which implies that $ux,vx,wy\notin E(\overline{G})$. Then, however, $ux,wy\in E(\overline{G})$, $u,w\in V_{1}$ and $x,y\in V_{i}$, and we have obtained a contradiction with the fact that $\mathcal{P}$ represents a harmonious coloring of $\overline{G}$. Thus $h(\overline{\epsilon(G)})\leq p\leq l=h(\overline{G})$. ∎

Let $G_{r,s}$ be the graph obtained by adding $s$ leaves to each vertex of the complete graph $K_{r}$. A vertex in the complete subgraph $K_{r}$ has degree $r+s-1$ in $G_{r,s}$, thus $h(G_{r,s})\geq r+s$. So, the diameter of $G_{r,s}$ is three. Moreover, there exists a harmonious homomorphism from $G_{r,s}$ to the graph $K_{r}+\overline{K_{s}}$ of order $r+s$ and diameter two, hence $h(G_{r,s})\leq r+s$. ∎

In any harmonious coloring of $G$, different points receive different colors, because every two points share a line, then $h(G)\geq q^{2}+q+1$.

We define the coloring in the points and lines as follows. We assign $q^{2}+q+1$ distinct colors to $q^{2}+q+1$ points of $PG(2,q)$. Now, if $a\not=0$, the line $[a,b]$ is colored with the color of the point $(a,b)$. Since $a^{2}\not=0$ implies $b\not=a^{2}+b$, $(a,b)$ is not incident to $[a,b]$. Then the partial coloring (defined at that moment) is proper. Moreover, for $\alpha\not=0$, if the point $(\alpha,\beta)$ is incident to the line $[a,b]$, $\beta=a\alpha+b$, then $(\alpha,\beta)\not=(a,b)$, and the point $(a,b)$ is not incident to the line $[\alpha,\beta]$, otherwise, $b=a\alpha+\beta=a\alpha+a\alpha+b$, i.e., $0=1+1$, a contradiction because $q$ is odd. Since for any pair of color classes $\{(a,b),[a,b]\}$ and $\{(m,n),[m,n]\}$ with $a\not=0$ and $m\not=0$ there is at most one edge joining them, the partial coloring is harmonious.

For $b\not=-1$, the line $[0,b]$ is colored with the color of the point $(0,b+1)$, the line $[0,-1]$ is colored with the color of the point $P$, and the line $L$ is colored with the color of the point $(0,0)$. Clearly, the partial coloring is proper. If a point $(0,b+1)$ is incident to the line $[a,b+1]$ then the point $(a,b+1)$ is not incident to the line $[0,b]$ since $b+1\not=b$. Therefore, the partial coloring is harmonious.

For $a\not=0,-1$, the line $L_{a}$ is colored with the color of the point $P_{a+1}$, the line $L_{-1}$ is colored with the color of the point $P_{1}$, and the line $L_{0}$ is colored with a new color. Clearly, the coloring is proper. Now, the point $P_{1}$ is incident to the line $[1,b]$ and $(1,b)$ is not incident to the line $L_{-1}$. If a point $P_{a+1}$ is incident to the line $[a+1,b]$, then the point $(a+1,b)$ is not incident to the line $L_{a}$ since $a+1\not=0$. Finally, the point $P$ is incident to the line $L_{a}$, the point $P_{a+1}$ is not incident to the line $[0,-1]$, and the point $P_{1}$ is incident to the line $L$, and the point $(0,0)$ is not incident to the line $L_{-1}$. Therefore, the coloring is harmonious and $h(G)\leq q^{2}+q+2$. ∎

The incidence graph $G$ of a linear space with point set $\mathcal{P}$ has $h(G)\geq|\mathcal{P}|=n$ by axiom 1. To get the upper bound, we assign a coloring via a line coloring with $\chi^{\prime}(\mathcal{S})$ colors and assign a different color to each vertex and the result follows because any two lines with the same color are at distance 3 or 4 in $G$. ∎

For the lower bound, let $G$ be the incidence graph of the complete graph $K_{n}$, with $V(K_{n})=\{x_{1},\dots,x_{n}\}$ and let $\varsigma:E(K_{n})\cup V(K_{n})\rightarrow\{c_{1},\dots,c_{h(G)}\}$ be a harmonious coloring.

By Theorem 10, $n\leq h(G)$. For each $x_{i}\in V(K_{n})$, let $c_{i}=\varsigma(x_{i})$. For each $i\in\{1,\dots,h(G)\}$, let $e_{i}=\{e\in E(K_{n}):\varsigma(e)=c_{i}\}$. Observe that each $e_{i}$ induces a matching in $K_{n}$, $\sum\limits_{i=1}^{h(G)}|e_{i}|=\binom{n}{2}$ and since $\varsigma$ is a harmonious coloring, for every $x_{i}\in V(K_{n})$, $x_{i}$ is not incident to an edge of $e_{i}$.

Let $G^{*}$ be the spanning subgraph of $K_{n}$ such that for each $xy\in E(G^{*})$, $\varsigma(xy)\in\{c_{1},\dots,c_{n}\}$. On the one hand, $e(G^{*})=\sum\limits_{i=1}^{n}|e_{i}|=\frac{1}{2}\sum\limits_{i=1}^{n}\deg_{G^{*}}(x_{i})$. On the other hand, for each $x_{i}\in V(G^{*})$, if there is $x_{i}x_{j}\in E(G^{*})$ such that $\varsigma(x_{i}x_{j})=c_{k}$, then $x_{k}$ is not incident to an edge of $e_{i}$. Thus, $|e_{i}|\leq\frac{n-1-\deg_{G^{*}}(x_{i})}{2}$.

Therefore $\frac{1}{2}\sum\limits_{i=1}^{n}\deg_{G^{*}}(x_{i})=\sum\limits_{i=1}^{n}|e_{i}|\leq\sum\limits_{i=1}^{n}\frac{n-1-\deg_{G^{*}}(x_{i})}{2}$ which implies that $\sum\limits_{i=1}^{n}\deg_{G^{*}}(x_{i})\leq\binom{n}{2}$. Thus, $e(G^{*})\leq\binom{n}{2}/2$ and therefore $\sum\limits_{j=n+1}^{h(G)}|e_{j}|\geq\frac{\binom{n}{2}}{2}$. Since, for each $i\in\{1,\dots,h(G)\}$, $|e_{i}|\leq\lfloor\frac{n}{2}\rfloor$ it follows that $(h(G)-n)\lfloor\frac{n}{2}\rfloor\geq\binom{n}{2}/2$. Finally we have

and from here the result follows.

For the upper bound suppose that $n=3m-l\geq 3$, where $m,l$ are integers and $0\leq l\leq 2$. Let $l_{0},l_{1},l_{2}$ be integers with $0=l_{0}\leq l_{1}\leq l_{2}\leq 1$ such that $l=l_{0}+l_{1}+l_{2}$. Consider a partition $\{V_{0},V_{1},V_{2}\}$ of $V(K_{n})$ with $|V_{i}|=m-l_{i}$, $i\in\{0,1,2\}$, and a partition $\{C_{0},C_{1},C_{2}\}$ of the set $\{1,\dots 3m\}$ with $C_{0}=\{1,\dots,m\}$, $C_{1}=\{m+1,\dots,2m\}$ and $C_{2}=\{2m+1,\dots,3m\}$. Since $l_{i}\in\{0,1\}$, we have $\chi^{\prime}(K_{n}[V_{i}])\leq\chi(K_{n}[V_{i}])=m-l_{i}\leq m$, and there is a proper edge coloring $\varsigma_{i}^{\prime}\colon E(K_{n}[V_{i}])\rightarrow C_{i+1\mod 3}$, $i\in\{0,1,2\}$. The graph $G^{\prime}=\overline{K_{n}[V_{0}]\cup K_{n}[V_{1}]\cup K_{n}[V_{2}]}\cong K_{m-l_{0},m-l_{1},m-l_{2}}$ satisfies $\Delta(G^{\prime})=2m-l_{1}$, hence, by Vizing’s Theorem, there is a proper edge coloring $\varsigma^{\prime}\colon E(G^{\prime})\rightarrow\{3m+1,\dots,5m-l_{1}+1\}$. Now define a coloring $\varsigma\colon V(G_{n})=V(K_{n})\cup E(K_{n})\rightarrow\{1,\dots,5m-l_{1}+1\}$ as follows:

1. 1.

   The restriction of $\varsigma$ to $V_{i}$ is an injection to $C_{i}$, $i\in\{0,1,2\}$.

2. 2.

   The restriction of $\varsigma$ to $E(K_{n}[V_{i}])$ is $\varsigma_{i}^{\prime}$, $i\in\{0,1,2\}$.

3. 3.

   The restriction of $\varsigma$ to $E(G^{\prime})$ is $\varsigma^{\prime}$.