Tight Bounds on 1-Harmonious Coloring of Certain Graphs

Abstract

Graph coloring is one of the most studied problems in graph theory due to its important applications in task scheduling and pattern recognition. The main aim of the problem is to assign colors to the elements of a graph such as vertices and/or edges subject to certain constraints. The 1-harmonious coloring is a kind of vertex coloring such that the color pairs of end vertices of every edge are different only for adjacent edges and the optimal constraint that the least number of colors is to be used. In this paper, we investigate the graphs in which we attain the sharp bound on 1-harmonious coloring. Our investigation consists of a collection of basic graphs like a complete graph, wheel, star, tree, fan, and interconnection networks such as a mesh-derived network, generalized honeycomb network, complete multipartite graph, butterfly, and Benes networks. We also give a systematic and elegant way of coloring for these structures.

1. Introduction

In mathematical sciences, graph coloring problems are very easy to state and visualize, but they have many aspects that are exceptionally difficult to solve [1]. This study traces back to the origin of the four-color problem of whether it is possible to color the regions of every map with four colors such that every two regions having a common boundary are assigned different colors. Later, it was seen that this is a problem in graph theory, whether it is always possible to color the regions of every planar graph (embedded in the plane) so that every two adjacent regions are colored differently [2]. It took more than 160 years and collective efforts to prove the simple-sounding proposition that four colors are sufficient to color the vertices of a planar graph properly [3]. Early research in this area was focused mostly on many theoretical aspects, particularly the statements concerning the chromatic number for specific topologies such as planar graphs, line graphs, random graphs, critical graphs, triangle-free graphs, and perfect graphs. Many of the real-world operational research problems can be tackled using graph coloring techniques, and these include disparate problem areas of producing sports schedules, solving Sudoku puzzles, checking for short circuits on printed circuit boards, assigning taxis to customer requests, timetabling lectures at a university, finding good seating plans for guests at a wedding, and assigning computer-programming variables to computer registers [1].

The harmonious coloring problem of a graph is to find the minimum number of colors needed to color the vertices of a graph such that the color pairs of end vertices of every edge are distinct. Hopcroft and Krishnamoorthy first established the abstraction of the harmonious coloring problem and proved the NP-completeness for general graphs [4]. Later [5], one more condition was added that adjacent vertices should receive distinct colors, and the minimum number is called the harmonious chromatic number. This number has been computed for graphs such as paths, two- and three-dimensional grids, complete binary trees, and graphs with a diameter at most two [5]. Therefore, there were contributions to finding the sharp bound for the graphs such as the collection of non-trivial disjoint paths, disjoint cycles, disjoint complete graphs, the disjoint union of two arbitrary complete binary graphs, trees, triangular snake graphs, double triangular snake graphs, and diamond snake graphs [6,7,8]. Apart from that, Lee and Mitchem [9] gave an upper bound for the harmonious chromatic number of a graph. As a consequence of this work, there were many improved results on the upper bound in several periods of time [10,11,12,13]. In [14], Wang et al. generalized the harmonious coloring problem and called it the local harmonious coloring problem, which is defined as follows.

The local harmonious coloring [14] is a d-harmonious coloring if every color-pair is present at most once for every edge within distance d of any vertex in that graph, and the d-harmonious chromatic number of G, denoted by $h_d\left(G\right)$, is the minimum k such that G has a d-harmonious coloring. Clearly, the original harmonious coloring problem is the $\lceil x/2\rceil$-harmonious coloring problem if x is the diameter of G. In addition, it was proven that solving the 1-harmonious coloring problem is NP-complete, and tight bounds were obtained for the path and cycle graphs, whereas the tight bounds for other graphs have been stated as open problems. Recently, Gao [15] presented three algorithms to give the coloring procedure for the 1-harmonious coloring problem, but these algorithms were based on an exhaustive search of vertices and branching rules.

The above study of the literature justifies the need for systematic mathematical expressions for the 1-harmonious coloring problem. In the present study, we obtained certain tight bounds to compute the 1-harmonious chromatic number. The rest of the paper is organized as follows: Section 2 contains the lower bound of a graph for the 1-harmonious coloring problem as $\Delta \left(G\right)+1$, where $\Delta \left(G\right)$ is the maximum degree of the graph G. In addition, we show the exact coloring for a number of graphs, which include grid and honeycomb networks. In Section 3, we obtain the lower bound for some special classes of graphs for which two or more vertices have $\Delta \left(G\right)$ number of common neighbors and show the exact coloring for the complete multipartite, fan, and Benes network. In Section 4, we connect the coloring numbers of a graph and its subgraph, followed by giving exact coloring for the butterfly network. Finally, we conclude the paper in Section 5.

2. Lower Bound

We begin this section with an observation that any vertex and all of its neighbors should be colored differently in order to produce the 1-harmonious coloring, and hence, we have the following result.

Theorem 1.

Let G be a simple connected graph. Then, $h_1\left(G\right)\ge \Delta \left(G\right)+1$.

It would be nice to see the implication of the above bound on basic graph structures such as path $P_n$ and cycle $C_n$ on n vertices each. In fact, the bound is sharp for any path, and interestingly, the bound is not exact for any cycle [14], as shown in Figure 1.

We now show the consequences of Theorem 1 for other basic graph structures as given in

Table 1. Exact 1-harmonious coloring of some graph structures.

S. No.	$\mathbf{Graph}\mathit{G}$	${\mathit{h}}_1\left(\mathit{G}\right)$
1	Complete graph	$\mid V\left(G\right)\mid$
2	Wheel
3	Star
4	Tree	$\Delta \left(G\right)+1$
5	Mesh Network
6	Extended Mesh Network
7	Generalized Honeycomb Network

.

Let $K_n$ be the complete graph on n vertices. Since each vertex in $K_n$ is adjacent to all the remaining $n-1$ vertices, we need n distinct colors to color $K_n$, and it is easy to conclude that $h_1\left(K_n\right)=\Delta \left(K_n\right)+1=n$. Similarly, let us consider a star graph $S_n$ and wheel graph $W_n$ on n vertices each. Since the center vertex of star graph (respectively wheel) is adjacent to all the remaining vertices, it is facile to color all the vertices with n distinct colors. Therefore, we conclude that $h_1\left(S_n\right)=h_1\left(W_n\right)=\Delta \left(G\right)+1=n$, as shown in Figure 2.

Let T be a tree on n vertices. Without loss of generality, we assume that a vertex v in T has the maximum degree and consider that T is rooted at v. Now, we show that $h_1\left(T\right)\le \Delta \left(T\right)+1$. Color the vertex v with 1 and all the vertices adjacent to v with a color set $\left\{2,3,\dots ,\Delta \left(T\right)+1\right\}$. Then, color the vertices at the next level, which are adjacent to the already colored vertex with i, $2\le i\le \Delta \left(T\right)+1$ using color set $\left\{2,3,\dots ,i-1,i+1,\dots ,\Delta \left(T\right)+1\right\}$. Continue this process till every vertex in the next level of T has been colored using the color set $\left\{1,2,\dots ,j-1,j+1,\dots ,k-1,k+1,\dots ,\Delta \left(T\right)+1\right\}$, where j is the color of the vertex at the current level and k is the color of the vertex in the previous level, which is adjacent to j. By Theorem 1, we conclude that $h_1\left(T\right)=\Delta \left(T\right)+1$.

2.1. Mesh Network

The topological structure of a mesh network is defined as the Cartesian product $P_m\times P_n$, $m,n\ge 2$, with m rows and n columns.

Theorem 2.

For $m,n\ge 2$, let G be an $m\times n$ mesh. Then, G admits a 1-harmonious coloring with chromatic number $h_1\left(G\right)=\Delta \left(G\right)$ + 1.

Proof. 

We show that $h_1\left(G\right)\le \Delta \left(G\right)$ + 1 by splitting the proof into two cases. Without loss of generality, we assume that $m\le n$.

Case 1: ($m$ = 2, $n\ge$ 2).

In this case, we color the first row vertices from left to right using color order $〈1,2,3,4〉$ and the second row vertices by $〈3,4,1,2〉$ repeatedly, as shown in Figure 3. It is clear that for each vertex, its adjacent vertices are colored differently, and by Theorem 1, $h_1\left(G\right)=4$.

Case 2: ($m,n$≥ 3).

We color the row i, $1\le i\le m$, by five-color set $\left\{1,2,3,4,5\right\}$ from left to right repeatedly as the order described in

Table 2. Color order of an $m\times n$ mesh.

S. No.	Row i	Color Order
1	i ($mod$ 5) = 1	$〈1,2,3,4,5〉$
2	i ($mod$ 5) = 2	$〈3,4,5,1,2〉$
3	i ($mod$ 5) = 3	$〈5,1,2,3,4〉$
4	i ($mod$ 5) = 4	$〈2,3,4,5,1〉$
5	i ($mod$ 5) = 0	$〈4,5,1,2,3〉$

. In what follows, i ($mod$ 5) is the remainder of $i/5$.

Table 2 shows that any vertex and its adjacent vertices are colored differently, resulting in $h_1\left(G\right)=5$. □

2.2. Extended Mesh Network

By replacing each 4-cycle in an $m\times n$ mesh into a complete graph on four vertices, we obtain an architecture called the extended mesh and denoted by $EX(m,n)$.

Theorem 3.

Let G be an extended mesh $EX$(m, n). Then, G admits 1-harmonious coloring with chromatic number $h_1\left(G\right)=\Delta \left(G\right)$ + 1.

Proof. 

It is easy to observe that $EX$(2, 2) is a complete graph $K_4$, and we conclude that $h_1\left(EX(2,2)\right)=4$. We now show that $h_1\left(G\right)\le \Delta \left(G\right)$ + 1 by splitting the proof as in Theorem 2. Without loss of generality, we assume that $m\le n$.

Case 1: ($m$ = 2, $n\ge$ 2).

We color the first row vertices from left to right using color order $〈1,2,3,4,5,6〉$ and the second row vertices by $〈4,5,6,1,2,3〉$ repeatedly, as shown in Figure 4. It is to be noted that every color pair is present at most once for every edge within distance one, and by Theorem 1, $h_1\left(G\right)=6$.

Case 2: ($m,n$≥ 3).

In this case, we color any row i, $1\le i\le m$, by nine-color set $\left\{1,2,3,4,5,6,7,8,9\right\}$ from left to right repeatedly as the order described in

Table 3. Color order of $EX$(m, n).

S. No.	Row i	Color Order
1	i ($mod$ 3) = 1	$〈1,2,3,4,5,6,7,8,9〉$
2	i ($mod$ 3) = 2	$〈4,5,6,7,8,9,1,2,3〉$
3	i ($mod$ 3) = 0	$〈7,8,9,1,2,3,4,5,6〉$

, and our coloring method results in $h_1\left(G\right)=9$. □

2.3. Generalized Honeycomb Network

The generalized honeycomb network [16] can be built from an infinite hexagonal system with no cut vertices or non-hexagonal interior faces. It is denoted by $GH(n,p,q,r,s)$, and the structure can be developed using hexagons in various ways by fixing the parameters as $n\ge 1$, $0\le p\le r\le n$, $0\le s\le q\le n$, and $p+q=r+s$, as shown in Figure 5. In particular, it generates the honeycomb network when $p=q=r=s=n-1$.

Theorem 4.

Let G be the generalized honeycomb network $GH(n,p,q,r,s)$. Then, G admits 1-harmonious coloring with chromatic number $h_1\left(G\right)=\Delta \left(G\right)+1$.

Proof. 

We show that $h_1\left(G\right)\le \Delta \left(G\right)+1$ by considering the elementary horizontal edge cuts $F_i$, $1\le i\le p+q+1$, as shown in Figure 6. The removal of all $F_i$’s in G results in $p+q+2$ number of paths and represented by $P^{\gamma }$, $1\le \gamma \le p+q+2$. Let $P_{v_1}^{\gamma }$ be the first vertex of $P^{\gamma }$. We now define a labeling function l from $\{P_{v_1}^{\gamma }:1\le \gamma \le p+q+2\}$ into $\{0,1,2,3\}$ as follows:

$$l\left(P_{v_1}^{\gamma }\right)=\left\{\begin{array}{cc}\gamma \left(mod4\right)\hfill & :1\le \gamma \le q+1\hfill \\ (2q+5-\gamma )\left(mod4\right)\hfill & :q+2\le \gamma \le p+q+2.\hfill \end{array}\right.$$

We now color the vertices of the paths $P^{\gamma }$ by $\left\{1,2,3,4\right\}$ from left to right repeatedly as the order described in

Table 4. Color order of the paths in $GH(n,p,q,r,s)$.

S. No.	$\mathit{l}\left({\mathit{P}}_{{\mathit{v}}_1}^{\mathit{\gamma }}\right)$	Color Order of ${\mathit{P}}^{\mathit{\gamma }}$
1	1	$〈1,2,3,4〉$
2	2	$〈2,3,4,1〉$
3	3	$〈3,4,1,2〉$
4	0	$〈4,1,2,3〉$

. By this coloring method and Theorem 1, we arrive at $h_1\left(G\right)=4$. □

3. Tight Bounds on Some Special Classes of Graphs

We begin this section by giving the definitions of the complete multipartite graph and fan graph. A graph $G=(V,E)$ is a t-partite, $t\ge 1$, if it is possible to partition $V\left(G\right)$ into t disjoint subsets $\{V_1,V_2,\dots ,V_t\}$ such that every edge in $E\left(G\right)$ joins a pair of vertices that come from two different partite sets. A complete multipartite graph G is a t-partite graph such that there is an edge between every pair of vertices from different partites and denoted by $K_{m_1,m_2,\dots ,m_t}$, where $m_i$ is the cardinality of $V_i$, $1\le i\le t$, See Figure 7a. A fan graph $F_{m,n}$ is obtained from $K_{m,n}$ by joining all the vertices in the second partite by a unique path, See Figure 7b.

Theorem 5.

For $k\ge 1$, let G be a connected graph such that k number of vertices have $\Delta \left(G\right)$ number of common neighbors. Then, $h_1\left(G\right)\ge \Delta \left(G\right)+k$.

Proof. 

Let $\left\{v_1,v_2,\dots ,v_k\right\}$ be the vertices of G such that each $v_i$ has $\Delta \left(G\right)$ number of common neighbors $w_j$, $1\le j\le \Delta \left(G\right)$. Without loss of generality, we color the vertex $v_1$ as 1. Then, it is obvious that the neighbors $w_j$ of $v_1$ should be colored with $\Delta \left(G\right)$ colors different from the color 1. Since each $w_j$ is adjacent to all the vertices $v_i$, we are forced to give the new colors to the vertices $\left\{v_2,v_3,\dots ,v_k\right\}$. Hence, $h_1\left(G\right)\ge \Delta \left(G\right)+1+(k-1)=\Delta \left(G\right)+k$. □

We now show the implication of the above theorem on some special classes of graphs such as a complete multipartite, fan graph, and Benes network.

Theorem 6.

The 1-harmonious coloring number of complete multipartite and fan graphs is given by $h_1\left(K_{m_1,m_2,\dots ,m_t}\right)=m_1+m_2+\dots +m_t$ and $h_1\left(F_{m,n}\right)=m+n$.

Proof. 

As $\mid V\left(K_{m_1,m_2,\dots ,m_t}\right)\mid =m_1+m_2+\dots +m_t$, it is enough to prove that $h_1\left(K_{m_1,m_2,\dots ,m_t}\right)\ge m_1+m_2+\dots +m_t$. Since $\Delta \left(K_{m_1,m_2,\dots ,m_t}\right)=m_1+m_2+\dots +m_k-min\{m_1,m_2,\dots ,m_k\}$ and from the construction of the complete multipartite graph, we observe that $min\{m_1,m_2,\dots ,m_k\}$ number of vertices have $\Delta \left(K_{m_1,m_2,\dots ,m_t}\right)$ common neighbors, and by Theorem 5, we arrive at $h_1\left(K_{m_1,m_2,\dots ,m_t}\right)\ge m_1+m_2+\dots +m_t$. Similarly, we can prove the fan graph. □

In what follows, $Q_n$ is the binary hypercube of dimension n and $V\left(Q_n\right)=\{x_1{x}_2\dots x_n:x_i\in \{0,1\},1\le i\le n\}$. For any positive integer $p,q$ and r, we denote $p_q=[\underset{q-\mathrm{times}}{\underbrace{p,p,\dots ,p}}]$ and ${〈p_q〉}_r=[\underset{r-\mathrm{times}}{\underbrace{p_q,p_q,\dots ,p_q}}]$.

The n-dimensional butterfly network, denoted by $BF\left(n\right)$, has a vertex set $V\left(BF\left(n\right)\right)=\{[x,i]:x\in V\left(Q_n\right),0\le i\le n\}$, and two vertices $[x,i]$ and $[y,j]$ are connected by an edge if and only if $j=i+1$ and either $x=y$ or x and y differ precisely in the $i^{\mathrm{th}}$ bit. Clearly, x and i represent the row and the level (column) of the vertex $[x,i]$ respectively, and the two-dimensional butterfly is depicted in Figure 8a. Further, the butterfly network was extended by adding n more levels, and resulting network is called the Benes network. Clearly, the n-dimensional Benes $B\left(n\right)$ has $2n+1$ levels with $2^n$ vertices in each level. The vertices from Level 0 to level n (respectively, n to $2n+1$) in $B\left(n\right)$ induce a $BF\left(n\right)$, and hence, the middle level of the Benes network is shared by two copies of butterfly networks [17], as shown in Figure 8b.

We now notice that Theorem 5 is extremely useful in proving a sharp bound for the Benes network and not in the case of the butterfly network, which is dealt with separately in the next section.

Theorem 7.

The Benes network $B\left(n\right)$ admits 1-harmonious coloring with chromatic number $h_1\left(B\left(n\right)\right)=6$.

Proof. 

From the definition of the Benes network, we have $\Delta \left(B\right(n\left)\right)=4$, and we further identify that the vertices $[x_1{x}_2\dots x_n,n]$ and $[x_1{x}_2\dots {\overline{x}}_n,n]$ of $B\left(n\right)$ have four common neighbors. Theorem 5 implies that $h_1\left(B\left(n\right)\right)\ge 6$. We now show that $h_1\left(B\left(n\right)\right)\le 6$ by defining a labeling function l from $\left\{\right[000\dots 0,i]:0\le i\le 2n\}$ into $\{0,1,2\}$ as follows:

$$l\left([000\dots 0,i]\right)=\left\{\begin{array}{cc}\left(2\right(n-i\left)\right)\left(mod3\right)\hfill & :0\le i\le n-1\hfill \\ (i-n)\left(mod3\right)\hfill & :n+1\le i\le 2n+1\hfill \end{array}\right.$$

Since $l\left(\right[000\dots 0,n\left]\right)=0$, we color the vertices at the $n^{\mathrm{th}}$ level as ${〈1,2〉}_{2^{n-1}}$ from top to bottom. Now, we color the vertices at the remaining levels using six-color set $\{1,2,3,4,5,6\}$ as the order described in

Table 5. The 1-harmonious coloring order for the levels of $B\left(n\right)$.

S. No.	$\mathit{l}\left(\right[00\dots 0],\mathit{i})$	Color Order of Level i from Top to Bottom
		$\mathit{i}=\mathbf{0},\mathbf{2}\mathit{n}$	$\mathbf{1}\le \mathit{i}\le \mathit{n}-\mathbf{1}$	$\mathit{n}+\mathbf{1}\le \mathit{i}\le \mathbf{2}\mathit{n}-\mathbf{1}$
1	0	$〈1_{2^{n-1}},2_{2^{n-1}}〉$	${〈1_{2^{n-i-1}},2_{2^{n-i}},1_{2^{n-i-1}}〉}_{2^{i-1}}$	${〈1_{2^{i-n-1}},2_{2^{i-n}},1_{2^{i-n-1}}〉}_{2^{2n-i-1}}$
2	1	$〈3_{2^{n-1}},4_{2^{n-1}}〉$	${〈3_{2^{n-i-1}},4_{2^{n-i}},3_{2^{n-i-1}}〉}_{2^{i-1}}$	${〈3_{2^{i-n-1}},4_{2^{i-n}},3_{2^{i-n-1}}〉}_{2^{2n-i-1}}$
3	2	$〈5_{2^{n-1}},6_{2^{n-1}}〉$	${〈5_{2^{n-i-1}},6_{2^{n-i}},5_{2^{n-i-1}}〉}_{2^{i-1}}$	${〈5_{2^{i-n-1}},6_{2^{i-n}},5_{2^{i-n-1}}〉}_{2^{2n-i-1}}$

.

Since all the vertices in each level are independent and each vertex $[x,i]$ has its neighborhoods only at the levels $i+1$ and $i-1$, the vertices of any three consecutive levels are colored with three distinct pairs of colors $\{1,2\}$, $\{3,4\}$ and $\{5,6\}$, respectively shown in Figure 9, and we have $h_1\left(B\left(n\right)\right)=6$. □

4. The 1-harmonious Coloring of the Butterfly Network

In this section, we first state the natural property of 1-harmonious coloring and then give the exact coloring for butterfly networks.

Theorem 8.

Let H be a subgraph of the graph G. Then, $h_1\left(H\right)\le h_1\left(G\right)$.

Theorem 9.

The butterfly network $BF\left(n\right)$ admits 1-harmonious coloring with chromatic number:

$$h_1\left(BF\left(n\right)\right)=\left\{\begin{array}{cc}4\hfill & \mathrm{if}n=1\hfill \\ 6\hfill & \mathrm{if}n\ge 2.\hfill \end{array}\right.$$

Proof. 

Since $BF\left(1\right)$ is $K_{2,2}$, we have $h_1\left(BF\left(1\right)\right)=4$. We now show that $BF\left(2\right)$ cannot be colored with five colors. Without loss of generality, let the color of vertex $[00,1]$ be $c\left(\right[00,1\left]\right)=1$. Then, its neighboring vertices $[00,0],[01,0],[00,2]$ and $[10,2]$ should be colored from the color set $\{2,3,4,5\}$ in some order. Again, without loss of generality, we assume that $c\left(\right[00,0\left]\right)=2$, $c\left(\right[01,0\left]\right)=3$, $c\left(\right[00,2\left]\right)=4$ and $c\left(\right[10,2\left]\right)=5$. In this case, the vertices $[01,1]$ and $[10,1]$ can be colored in the following ways:

(i)

$c\left(\right[01,1\left]\right)=4$ or 5,

(ii)

$c\left(\right[10,1\left]\right)=2$ or 3.

We start with the first case $c\left(\right[01,1\left]\right)=4$ and $c\left(\right[10,1\left]\right)=2$. Since $c\left(\right[01,1\left]\right)=4$, we can color the vertices $[01,2]$ and $[11,2]$ using the color set $\{1,5\}$ in some order. Let us assume that $c\left(\right[01,2\left]\right)=1$ and $c\left(\right[11,2\left]\right)=5$. Similarly, since $c\left(\right[10,1\left]\right)=2$, we can color the vertices $[10,0]$ and $[11,0]$ using the color set $\{1,3\}$ in some order. However, whatever may be the order, the vertex $[11,1]$ is now adjacent to two vertices colored with 1. Therefore, $h_1\left(BF\left(2\right)\right)>5$. In the same manner, we can prove the other three cases that $h_1\left(BF\left(2\right)\right)>5$, as shown in Figure 10.

By Theorem 8, we have $h_1\left(BF\left(n\right)\right)\ge h_1\left(BF\left(2\right)\right)\ge 6$, and we now color the vertices of $BF\left(n\right)$ with six colors. First, we color the vertices at Level 0 as ${〈1,2〉}_{2^{n-1}}$ from top to bottom. Now, we color the vertices at the remaining levels using six-color set $\{1,2,3,4,5,6\}$ as the order described in

Table 6. The 1-harmonious coloring order for the levels of $BF\left(n\right)$.

S. No.	Level i	Color Order of Level i
		$\mathbf{1}\le \mathit{i}\le \mathit{n}-\mathbf{1}$	$\mathit{i}=\mathit{n}$
1	i ($mod$ 3) = 0	${〈1_{2^{i-1}},2_{2^i},1_{2^{2^{i-1}}}〉}_{2^{n-i-1}}$	$〈1_{2^{n-1}},2_{2^{n-1}}〉$
2	i ($mod$ 3) = 1	${〈3_{2^{i-1}},4_{2^i},3_{2^{2^{i-1}}}〉}_{2^{n-i-1}}$	$〈3_{2^{n-1}},4_{2^{n-1}}〉$
3	i ($mod$ 3) = 2	${〈5_{2^{i-1}},6_{2^i},5_{2^{2^{i-1}}}〉}_{2^{n-i-1}}$	$〈5_{2^{n-1}},6_{2^{n-1}}〉$

.

The way in which we colored the butterfly network is similar to the Benes network, and following the proof technique of Theorem 7 as illustrated in Figure 11, we arrive at $h_1\left(BF\left(n\right)\right)=6$. □

5. Concluding Remarks

In this paper, we presented a lower bound for 1-harmonious coloring that the graph G with k ($k\ge 1$) number of vertices having $\Delta \left(G\right)$ common neighbors needs at least $\Delta \left(G\right)+k$ colors. We applied this bound to certain basic graph structures and symmetrical interconnection networks such as mesh, honeycomb, butterfly, and Benes, in order to show the bound is tight. Finally, we believe that our bound will explore many more graphs, for instance cube-connected cycles, and will naturally extend to n-harmonious coloring.