pproximate and exact results for the harmonious chromatic numbe



Introduction
============

A key topic in the area of graph theory is represented by graph colorings. The proper vertex $k$-coloring is perhaps the most famous type of coloring and has many applications such as scheduling, pattern matching, exam timetabling, seating plans design (see  @zhang2016kaleidoscopic [@utility]). There are numerous types of colorings, e.g., harmonious, graceful, metric, sigma, set, multiset (see @zhang2016kaleidoscopic and the references therein).

In this paper we focus on harmonious colorings. We consider only finite undirected graphs $G(V,E)$, with $|V|$ vertices (or nodes) and $|E|$ edges. Given a graph $G$, we denote by $V(G)$ the set of vertices of $G$ and by $E(G)$ the set of edges of $G$, respectively. Given a positive integer $k$, let $[k] = \{1, 2, \dots, k\}$.

Preliminaries and previous work
-------------------------------

The concept of harmonious coloring was proposed independently by @frank1982line and by @hopcroft1983 and defined below.

\[Harmonious coloring\]  \[HarmoniousColoring\] Let $G$ be a graph and $c: V(G)\rightarrow [k]$ be a proper vertex coloring of $G$. The coloring $c$ is called harmonious if for every two distinct colors $i, j \in [k]$ there is at most one pair of adjacent vertices in $G$ colored with $i$ and $j$.

The definition of harmonious coloring leads to next observation.

 \[obs:harmonious-distinct\] There exists at least one harmonious coloring in any graph, since coloring all vertices with distinct colors produces a harmonious coloring.

The existence of the harmonious coloring of the graph follows from Observation \[obs:harmonious-distinct\]. We are interested in finding the minimum number of colors required to have a valid harmonious coloring, that is to find the harmonious chromatic number of a graph, as defined next.

\[The harmonious chromatic number\]  \[Harmonious\_chromatic\_number\] The minimum positive integer $k$ for which a graph $G$ has a harmonious $k$-coloring is called the harmonious chromatic number of $G$ and is denoted by $h(G)$.

We can associate to a harmonious $k$-coloring $c$ of $G$ an edge coloring $c'$ of $G$ as follows: each edge $uv$ is assigned the color $c'(uv)=\{c(u),c(v)\}$. A color $c'(uv)$ is a $2$-element subset of the set of colors assigned to the vertices of $G$. In the resulting edge coloring $c'$ all the edges are colored with distinct colors. Thus, it follows that ${k \choose 2} \geq |E|$.

Note that the harmonious coloring is different than the harmonious labeling of a graph, introduced by @GrahamSloane. In a harmonious labeling $c$ of an undirected graph $G$ the colors of vertices are elements of $\mathbb Z_k$ (set of integers modulo $k$) and the induced edge-coloring $c'$ is defined as $c'(uv)= (c(u)+c(v)) (\mbox{mod } k) $.

### Known results related to the computational complexity of the harmonious coloring problem 

@hopcroft1983 show that the harmonious coloring problem for arbitrary graphs is NP-complete. Moreover, determining whether a graph has a harmonious coloring using at most $k$ colors is known to be NP-complete even in trees (@edwards1995complexity), split graphs (@interval_permutation), interval graphs (@interval_permutation [@bodlander1989cograph]) and several other classes of graphs (@bodlander1989cograph [@edwards_1997; @edwards1995complexity; @interval_permutation; @subclasses_2010; @asdre_2007_NP_classes]). Polynomial time algorithms are known for some special classes of graphs (@miller1991), the most important being for trees of bounded degree (@edwards_1996).

A recent paper that deals with the computational aspects of harmonious coloring is (@kolay2019harmonious). In this paper the authors list the classes of graphs for which the harmonious coloring is known to be NP-hard.

@kolay2019harmonious study the parameterized complexity of the harmonious coloring problem under various parameters such as solution size, above or below known guaranteed bounds and vertex cover number of the graph.

### Known upper and lower bounds for the harmonious chromatic number

By Observation \[obs:harmonious-distinct\], we have $h(G)\le |V(G)|$. Lower bounds for the harmonious chromatic number of a graph $G$ of size $m$ and maximum degree $\Delta$ are given in @zhang2016kaleidoscopic and stated next.

\[@zhang2016kaleidoscopic\]\[lower\_m\] If G is a graph of size m, then $$h(G) \geq \left \lceil  \frac  {1+ \sqrt{8m+1}}{2} \right \rceil  .$$

We recall the following theorem that relates the harmonious chromatic number and the maximum degree of a graph.

\[@zhang2016kaleidoscopic\] \[the:delta\] If $G$ is a graph having maximum degree $\Delta$, then $$h(G) \geq \Delta + 1 .$$

\[cor: complementary\] For a graph G of order $n \geq 2$, $h(G)= 1$ if and only if $ G =\overline { K_n }$. Furthermore, $h(K_n) = n$.

\[lower\_bond\] Any graph of order $n$ having maximum degree $n-1$ has harmonious chromatic number $n$.

@LeeMitchem present an upper bound for the harmonious chromatic number of a graph.

\[@LeeMitchem\]\[uper\_bound\] If $G$ is a graph of order n having maximum degree $\Delta$, then $$h(G)\leq (\Delta^2+1)\lceil \sqrt n \rceil.$$

@McDiarmid1991 determined an improved upper bound for the harmonious chromatic number of a graph.

\[@McDiarmid1991\] If $G$ is a nonempty graph of order $n \geq 2$ having maximum degree $\Delta$, then $$h(G)\leq 2 \Delta \sqrt {n-1} .$$

### Previous results for harmonious chromatic number on particular classes of graphs {#sec:previous_particular}

Concerning *the exact value of the harmonious chromatic number of a graph*, there are only few graphs for which the precise value of the harmonious chromatic number is known. The harmonious chromatic number of the path with $n$ vertices $P_n$ has been determined by @lu1, and of cycles $C_n$ by @Mitchem1. The harmonious chromatic number of a class of caterpillars with at most one vertex of degree more than $2$ (paths, stars, shooting stars and comets), and an upper bound of the harmonious chromatic number of $3$-regular caterpillars were found by @article. Harmonious coloring has been studied for distance degree regular graphs of diameter $3$ and for several particular classes of graphs such as Parachute, Jellyfish, Gear, and Helm graph by @huilgol2016harmonious.

The harmonious chromatic number for the central graph, middle graph, and total graph of some families of graphs was studied in various papers: prism graph by @article_MYn_CYn; flower graph, belt graph, rose graph and steering graph by @central; snake derived architecture by @snake_graphs; Jahangir graph by @jahangir_graph; star graph by @line_star, and double star graph by @double_star.

Next we present a couple of known results related to graphs with diameter $2$. Recall that the *distance* $d(u,v)$ between two vertices is the length of a shortest $u-v$ path in a graph $G(V,E)$, and the *diameter* $diam(G)$ is the largest distance between any two vertices of $G$.

\[folklore\] \[the:dist2\] Let $G$ be a graph with diameter 2 and $v$ be an arbitrary vertex of $G$. Denote by $N_2[v]$ the set of vertices at distance at most $2$ from $v$, including $v$. Then, in a harmonious coloring of $G$, vertices from $N_2[v]$ receive distinct colors.

Let $c$ be a harmonious coloring of $G$. Assume by contradiction that two vertices $a,b \in N_2[v]$ have the same color, i.e. $c(a) = c(b)$. Then we have two cases. In the first case, $a$ and $b$ are adjacent vertices; the fact that they have the same color contradicts the definition of a harmonious coloring. In the second case, assume that $a$ and $b$ are at distance $2$. Thus, there exists a vertex $x \neq a, x \neq b$ such that $(a,x) \in E$ and $(b,x) \in E$. Since $a$ and $b$ have the same color, it follows that $\{c(a),c(x)\} = \{c(b),c(x)\}$, which again contradicts the definition of a harmonious coloring. Thus, the theorem holds.

\[folklore\]\[cor:diameter\_2\] Any graph $G$ with $n$ vertices and diameter $2$ has the harmonious chromatic number $n$.

In a graph with diameter $2$, all the vertices are at distance at most $2$ and, thus, according to Theorem \[the:dist2\], all the vertices in the graph must receive distinct colors.

Among the most known graphs with diameter two are individual graphs like complete bipartite graph $K_{3,3}$, Wagner graph, Moser Spindle graph, Golden-Harary graph, Fritsch graph, Petersen graph, house graph, prism graph $Y_3$, octahedron graph and some classes of graphs like cographs, the friendship graphs, the fan graphs, the wheel graphs.

Our results
-----------

In this paper we show the following results. In Section \[sec:computation\] we tackle the harmonious coloring problem from the computational point of view. More precisely, we show that the harmonious coloring problem cannot be approximated within a factor of $1.17 - \epsilon$, assuming $P \neq NP$ and within a factor $4/3 - \epsilon$, assuming the Unique Games Conjecture, $\forall \epsilon > 0$. We prove our hardness results by generalizing the NP-hardness reduction of @complete. We also show why the natural greedy algorithm (that colors vertices one by one and assigns the smallest color possible) is not a good approximation. In the last part of Section \[sec:computation\], we present a relation between the harmonious chromatic number and the minimum vertex cover.

Then, in Section \[sec:particular\_classes\] we determine exact values of the harmonious chromatic number for particular classes of graphs, like $(3,3)$-regular planar and non-planar graphs and some families of cycle-related graphs. Some of these results are obtained using a backtracking based computer program.

Computational results on harmonious coloring {#sec:computation}
============================================

In this section we aim to tackle the computational complexity of the harmonious coloring.

Hardness of approximation of harmonious coloring on general graphs
------------------------------------------------------------------

In this subsection we show that the harmonious coloring APX-hard or that it does not admit a polynomial time approximation scheme. In other words, there exists a constant $c$ such that the harmonious coloring number on general graphs cannot be approximated within a factor of $c$.

There exists a constant $c < 1.17$ such that the harmonious coloring problem cannot be approximated within a factor of $c$, unless $P = NP$. Moreover, if we assume the Unique Games Conjecture, the harmonious coloring problem cannot be approximated within a factor of $4/3 - \epsilon$ for any $\epsilon > 0$.

We show our result via a reduction from the Independent Set problem. Our reduction is a simple modification of the reduction of @complete. Given a graph $G = (V,E)$ for which we aim to find an independent set with $k\le |V|$ elements, we can construct in polynomial time an instance of the harmonious coloring problem for a graph with two connected components $G'$ and $G''$. The first component $G'$ has vertex set $V \cup \{v_1, v_2, v_3\}$. The set of edges of $E(G')$ is obtained by adding at $E(G)$ edges between every vertex of $G$ and $v_1, v_2,$ and $v_3$, respectively, and edges $\{v_1,v_2\}$, $\{v_2,v_3\}$, $\{v_1,v_3\}$. The second component $G''$ is a clique with $|V|$ vertices.

Observe that $G'$ cannot be harmoniously colored with less than $|V| + 3$ colors, since it has diameter less or equal than $2$ (Corollary \[cor:diameter\_2\]).

The claim is that this two-component graph can be harmoniously colored with $2|V| + 3 - k$ colors if and only if $G$ has an independent set of size $k$.

Assume first that $G$ has an independent set $X$ of size $k$. We define a harmonious coloring for the two-component graph as follows: color vertices of $G'$ with distinct colors; then color $|X|$ vertices of $G''$ with the colors used for the vertices of $X$ in $G'$ and the rest of the vertices of $G''$ with $|V|-|X|$ new colors. The obtained coloring is obviously harmonious and uses $|V|+3+|V|-|X|=2|V|+3-|X|$ colors.

Conversely, assume that the two-component graph has a harmonious coloring with $2|V| + 3 - k$ colors. For $k=1$ there is obviously an independent set of size $k$ in $G$. Assume $k\ge 2$. For the vertices in component $G'$ exactly $|V|+3$ distinct colors are used (Corollary \[cor:diameter\_2\]). We have $|V|-k$ unused colors left only for vertices in $G''$. Since $G''$ is a clique, vertices from $G''$ have distinct colors. It follows that there are $k$ colors used both for vertices in $G'$ and in $G''$. By the definition of a harmonious coloring, it follows that in $G'$ these vertices form an independent set. This independent set is also an independent set in $G$, since vertices $v_1$, $v_2$, $v_3$ are pairwise adjacent and adjacent to all the vertices in $G$.

Let $0 < s < c \le \frac{1}{2}$ be constants and let $GapIS(c,s)$ be a "promise gap problem" where an $n$-vertex graph is given with the promise that either it contains an independent set of size $cn$ or contains no independent set of size $sn$ and the algorithmic task is to distinguish between the two cases. According to our reduction, we have that if $GapIS(c,s)$ is NP-hard, then the harmonious coloring is NP-hard to approximate within $$\frac{2|V| + 3 - s|V|}{2|V| + 3 - c|V|}.$$ Thus, harmonious coloring is NP-hard to approximate within $\frac{2-s}{2-c} + \epsilon$, for some $\epsilon > 0$.

The best gap known is of @Dinur04onthe and has $GapIS(1 - 2^{-1/d} - \epsilon, \epsilon)$ for $d \ge 2$. Thus, for $d=2$, we have that the harmonious coloring is hard to approximate within $\frac{2}{1 + \frac{1}{\sqrt{2}}} \approx 1.17$, unless $P = NP$. Then, according to @khot2008vertex, assuming the Unique Games Conjecture we have $GapIS(1/2 - \epsilon, \epsilon)$. Thus, assuming the Unique Games Conjecture, the harmonious coloring problem is hard to approximate within a factor of $4/3 - \epsilon$.

The natural greedy algorithm is an $\Omega(\sqrt{n})$-approximation 
--------------------------------------------------------------------

A natural greedy algorithm to harmoniously color a graph is as follows. Process the vertices arbitrarily and color each vertex with the smallest available color, i.e., smallest color that keeps the coloring up to these step harmonious. In this section we show that this greedy algorithm is a $\Omega(\sqrt{n})$-approximation even in the case of trees, where $n$ is the number of nodes in the tree. The result is stated in the next theorem.

There exists a tree $T$ with $n = N(N-1)$ vertices that has a harmonious coloring with $2N - 2$ colors and is colored by the greedy algorithm with $(N-1)^2+1$ colors for a certain ordering of its vertices.

The tree $T$, illustrated in Figure \[fig:counterex\_greedy\] is defined as follows. The root $a_0$ has $N-1$ children $a_1, \dots, a_{N-1}$. Each of the $N-2$ nodes $a_2, \dots, a_{N-1}$ has only one children. We term the children of the node $a_i$ with $b_i$. Then, each of the nodes $b_2, \dots b_{N-1}$ has $N-1$ children. We denote the $N-1$ children of the node $b_i$ as $c^1_{i}, c^2_{i}, \dots, c^{N-1}_{i}$. Tree $T$ has $n = N + N-2 + (N-1)(N-2) = N(N-1)$ vertices.

The greedy algorithm colors the root $a_0$ with $1$, $a_1$ with $2$, and the nodes $a_2, \dots, a_{N-1}$ with colors $3, 4, \dots, N$. Then, each of the nodes $b_2, \dots, b_{N-1}$ have color $2$. Finally, each of the nodes $c^j_{i}$ have a distinct color, which results in a total of $N + (N-1)(N-2)=(N-1)^2+1$ colors.

A coloring with $2N - 2$ is as follows. The root $a_0$ is colored with $1$ and the vertices $a_2, \dots, a_{N-1}$ with colors $2, 3, \dots, N$. In turn, the nodes $b_2, \dots, b_{N-1}$ are colored with colors $N+1, N+2, \dots, 2N - 2$. Finally, for every $2\le i\le N-1$ the nodes $c_i^j$ with $1\le j\le N-1$ are colored with the colors from the set $\{1,2,\dots,N\}$ different than the color of $a_i$.

Therefore, the greedy algorithm has an approximation factor of $\Omega(N) = \Omega(\sqrt{n})$.

![Counterexample for the greedy algorithm<span data-label="fig:counterex_greedy"></span>](n_tree)

Relating the harmonious coloring to the size of a minimum vertex cover
----------------------------------------------------------------------

In this subsection we show a connection between the harmonious chromatic number and the size of a minimum vertex cover of a graph. Before we present our theorem, we remind the definition of the vertex cover.

Given an undirected graph $G=(V,E)$, a subset $V' \subseteq V$ is a vertex cover of $G$ if for any edge $(a,b) \in E$ we have that either $a \in V'$, $b \in V'$ or both $a,b \in V'$.

Finding the minimum vertex cover is a classical NP-hard problem for which the best approximation algorithm has a factor of 2 (see @Vazirani10). We now state our result.

For any undirected graph $G = (V,E)$ we have that $h(G) \le VC + \Delta^2 - \Delta+1$, where $VC$ is the size of a minimum vertex cover of $G$ and $\Delta$ is the maximum degree of $G$.

Let $V'$ be a minimum vertex cover of $G$ and let $VC = |V'|$. For a vertex $x \in V$ let $N(x)$ be the open neighborhood of $x$, that is $N(x)= \{y \in V : (x,y) \in E\}$. For a set of vertices $X \subseteq V$, let $N(X)$ be set of all neighbours of vertices in $X$, that are not in $X$, that is $N(X) = \{b \in V - X : \exists a \in X \text{ s.t. } (a,b) \in E \}$.

We show a simple algorithm that colors any undirected graph with $VC + \Delta^2 - \Delta+1$ colors. First, we color the vertices of $V'$ with distinct colors from the set $\{1,2 \dots, VC \}$. Then, we process the vertices in $V - V'$, one by one in an arbitrary order and we color them as follows. For each vertex $x \in V - V'$ we simply assign one of the colors in the set $\{VC + 1, \dots, VC + \Delta^2 - \Delta +1\}$ such that the coloring remains harmonious.

We now show that there always exist one such color in the set $\{VC + 1, \dots, VC + \Delta^2 - \Delta +1 \}$. More exactly, we prove that for a vertex $x \in V - V'$ there are at most $\Delta^2 - \Delta$ vertices in $V - V'$ that are at distance at most $2$ from $x$, hence require a color different that $x$.

Let $x \in V - V'$. First note that $N(x) \subseteq V'$, since two vertices that are not in the vertex cover cannot be neighbours (otherwise, the definition of the vertex cover is violated). Consider now $N(N(x))$. Since the maximum degree of a vertex in $N(x)$ is $\Delta$ and each vertex in $N(x)$ is adjacent to $x$, it follows that there are at most $(\Delta-1)|N(x)|$ vertices in $N(N(x))-\{x\}$. But $|N(x)|\le \Delta$, hence there are at most $(\Delta-1)\Delta $ vertices in $V-V'$ that are at distance at most $2$ from $x$.

Exact value of the harmonious chromatic number for some particular graphs, and classes of graphs {#sec:particular_classes}
================================================================================================

In this section we determine the harmonious chromatic number for some families of graphs like regular graphs and cycle-related graphs. We remind that the results for the graphs with diameter $2$ are presented in Section \[sec:previous\_particular\].

3-regular graphs of diameter 3
------------------------------

First, recall the definition of a regular graph.

\[def:regular-graph\] A connected graph $G$ is a regular graph if every vertex of $G$ has the same number of neighbors, so every vertex has the same degree. A regular graph with vertices of degree $r$ is called a $r‑regular$ graph or regular graph of degree $r$.

Corollary \[cor:diameter\_2\] refers to any graphs with diameter two, including $r$-regular graphs. Thus, the next statement follows.

\[regular\_2\] All $r$-regular graphs $G$ with $n$ vertices and diameter 2 have harmonious chromatic number $n$.

For example, octahedron is a $4$-regular graph with diameter $2$ (Figure \[fig:octahedron\]), Wagner graph (Figure \[fig:wagner\]) and Petersen graph (Figure \[fig:petersen\]) are $3$-regular graphs of diameter $2$, hence they have the harmonious chromatic number $n$.

\[b\]<span>0.3</span>![A harmonious 10-coloring of Petersen graph<span data-label="fig:petersen"></span>](h_octahedron_graph "fig:")

\[b\]<span>0.3</span>![A harmonious 10-coloring of Petersen graph<span data-label="fig:petersen"></span>](images/h_Wagner_graph "fig:")

\[b\]<span>0.3</span>![A harmonious 10-coloring of Petersen graph<span data-label="fig:petersen"></span>](images/h_petersen "fig:")

A graph with maximum degree $\Delta$ and diameter $diam$ is called a $(\Delta, diam)$-graph. We determine the harmonious chromatic number for all $(3,3)$-regular planar graphs, and for well known $(3,3)$-regular non-planar graphs. @all_3_regular give a list of $3$-regular graphs of diameter $3$.

\[prop:min\_7\] For a $(3,3)$-regular graph $G$ the minimum number of colors for a harmonious coloring is $7$.

Let $G(V,E)$ be a $(3,3)$-regular graph. Then, obviously, $|V(G)| \ge 8$. Let $c$ be a harmonious coloring of $G$. If all colors are distinct, then at least $8$ colors are used. Otherwise, there are two distinct vertices $v$, and $u$ with $c(u)=c(v)$. Then, vertices from $N(u)\cup N(v)$ must have distinct colors, different from $c(u)$. Since $c(u)=c(v)$, we have $d(u,v)\ge 3$ and $N(u)\cap N(v)=\emptyset$. It follows that there are $6$ vertices in $N(u)\cup N(v)$, all having distinct colors, different from $c(u)$, hence at least $7$ colors are used.

### Planar $(3,3)$-regular graphs

@pratt1996complete establishes that the smallest $3$-regular planar graph with the diameter $3$ has $8$ vertices and the largest $3$-regular planar graph with the diameter $3$ has $12$ vertices. The number of non isomorphic planar $(3,3)$-regular graphs with $8$ vertices is $3$, with $10$ vertices is $6$, and with $12$ vertices is $2$. Note that an $r$-regular graph with $r$ odd must have an even number of vertices (Handshaking lemma).

Figure \[fig:graph\_3\_3\] displays all the $(3,3)$-regular planar graphs with 8 vertices. Figure \[fig:graph\_3\_3\_10\] display all $(3,3)$-regular planar graphs with 10 vertices. Figure \[fig:truncated\_tetrahedron\] display the two $(3,3)$-regular planar graphs with $12$ vertices.

![Harmonious 7-colorings of all (3,3)-regular planar graphs with 8 vertices<span data-label="fig:graph_3_3"></span>](graph_3_3_8)

\[harmonious\_3\_3\_8\] For $(3,3)$-regular graphs with $8$ or $10$ vertices the harmonious chromatic number is 7.

From Proposition \[prop:min\_7\], the number of colors for a harmonious coloring of a $(3,3)$-regular graph with $8$ or $10$ vertices is at least $7$. Then, to prove the result, it suffices to provide $7$-harmonious colorings for these graphs. In Figure \[fig:graph\_3\_3\] we present all planar $(3,3)$-regular graphs with $8$ vertices along with a $7$-harmonious coloring of each of them and in Figure \[fig:graph\_3\_3\_10\] we present harmonious colorings with $7$ colors for each planar $(3,3)$-regular graphs with $10$ vertices.

![Harmonious 7-colorings of all $(3,3)$-regular planar graphs with 10 vertices<span data-label="fig:graph_3_3_10"></span>](h_graph_3_3_10_6)

\[th12vf\] The harmonious chromatic number for the only 2 planar (3,3)-graphs with 12 vertices is 8.

Figure \[fig:truncated\_tetrahedron\] shows a harmonious $8$-coloring of the truncated tetrahedron graph and a harmonious $8$-coloring of the second $(3,3)$-regular planar graph with $12$ vertices.

Using a computer program, we proved that these graphs cannot be colored harmoniously with less colors, by exhaustively trying all the possible harmonious colorings with $7$ colors. Our program is based on the classical backtracking schema: we color vertices one by one in increasing order of their index, and at one step we verify that there are no conflicts for the color $c$ assigned to the current vertex by considering the colors of the neighbours of all vertices previous colored with $c$.

The source code of the program used in the proof of Theorem \[th12vf\] is available at @link_program.

### Non-planar (3,3)-regular graphs

In the previous section we determined the harmonious chromatic number for all $(3,3)$-regular planar graphs. It is natural to study the harmonious chromatic number for $(3,3)$-regular graphs with $10$ or $12$ vertices that are no longer planar. A list of these graphs (described via their adjacency lists) can be found at @link_33.

Using the program described in the proof of Theorem \[th12vf\], we find that all non-planar $(3,3)$-regular graphs with $10$ vertices have harmonious chromatic number between $7$ and $9$ ($7$ in the planar case). One well-known non-planar $(3,3)$-regular graphs with $10$ vertices, the pentagonal prism graph $GP_{5,1}$, has $h(GP_{5,1})=7$ (Figure \[fig:pentagonal\]). Figure \[fig:doi\_10vertices\] shows two other $(3,3)$-regular non-planar graphs with 10 vertices, one with $h=8$, and one with $h=9$ (this is the only graph of this type that has $h=9$).

\[b\]<span>0.35</span>![Harmonious coloring of two $3$-regular graphs with 10 vertices<span data-label="fig:doi_10vertices"></span>](h_pentagonal_prism "fig:")

\[b\]<span>0.55</span>

According to @pratt1996complete, there are $32$ $(3,3)$-regular non-planar graphs with $12$ vertices, among which Franklin graph (Figure \[fig:franklin\]), Yutsis graph (Figure \[fig:Yutsis\]), and Tietze's graph (obtained from Petersen graph by expanding one vertex to a triangle; Figure \[fig:tietze\]), all having harmonious chromatic number $h=9$, and Bidiakis graph (Figure \[fig:bidiakis\]), with $h=8$.

\[b\]<span>0.45</span>![A harmonious 8-coloring of Bidiakis graph<span data-label="fig:bidiakis"></span>](h_Franklin.jpg "fig:")

\[b\]<span>0.45</span>

\[b\]<span>0.42</span> ![A harmonious 8-coloring of Bidiakis graph<span data-label="fig:bidiakis"></span>](h_Tietze.jpg "fig:")

\[b\]<span>0.45</span>![A harmonious 8-coloring of Bidiakis graph<span data-label="fig:bidiakis"></span>](h_bidiakis_8.jpg "fig:")

The $(3,3)$-regular non-planar graphs can have more than $12$ vertices. Although we could not classify all $(3,3)$-regular graphs according to their harmonious chromatic number, we fully explore the planar graphs from this category and provide a tool - a computer program - to explore the harmonious coloring of these graphs when the number of vertices is small enough. The harmonious chromatic number for other interesting $3$-regular graphs up to $24$ vertices obtained using our computer program can be found in  @link_program.

Some families of cycle-related graphs
-------------------------------------

In previous work are determined the value of the harmonious chromatic number for some graphs generated from a cycle, like wheel graph $W_n$, gear graph $G_n$, and Helm graph $H_n$ by @huilgol2016harmonious. These graphs have $n$ vertices on a cycle connected to a central vertex, and then $\Delta=n$. The harmonious chromatic number is $h(W_n)=h(G_n)=h(H_n)=n+1$.

Next, we determine de exact values for the harmonious chromatic number of other families of cycle-related graphs, like: sunflower graph, flower graph, double wheel graph, sun graph, closed sun graph, and lollipop graph.

### Cycle-related graphs with diameter $2$

The are several interesting cycle-related graphs with diameter $2$, like the followings. Each of these graphs has $2n+1$ vertices, and $\Delta=2n$. Thus, from Corollary \[cor:diameter\_2\], the harmonious chromatic number is equal with the number of their vertices, $h= 2n+1$.

-   Flower graph $Fl_n$, obtained from Helm graph $H_n$ by joining every pendant with the central vertex (see Figure \[fig:Flower\]).

-   Double wheel graph $W_{n,n}$, obtained from two wheel graphs $W_n$ sharing the same universal vertex (also called center) $v_0$, with vertices on the cycle denoted $v_1,v_2,\dots,v_n$, respectively $u_1,u_2,\dots,u_n$ (see Figure \[fig:double\_wheel\]).

-   The graph <span>$G_{n,n}$</span>, obtained from $W_{n,n}$ by connecting $v_i$ with $u_i$, where $1\leq i\leq n$ (see Figure \[fig:new\_prism\]).

-   Triangular book $B_{3,n}$, defined by set of vertices $V=\{v,u,v_i: 1\leq i\leq n\}$ and set of edges $E=\{uv,uv_i,vv_i: 1\leq i\leq n\}$ (see Figure \[fig:book\]).

-   Triangular book with bookmark $TB_{3,n}$, defined by set of vertices $V=\{v,u,x,v_i: 1\leq i\leq n\}$ and set of edges $E=\{uv,ux,uv_i,vv_i: 1\leq i\leq n\}$ (see Figure \[fig:book\_mark\]).

-   Jewel graph $J_n$, defined by the set of vertices $V=\{u,v,x,y,v_i:1\leq i \leq n\}$, and the set of edges $E=\{ux,xv,xy,uy,yv,uv_i, vv_i:1\leq i \leq n\}$ (see Figure \[fig:jewel\]).

\[b\]<span>0.3</span> ![ A harmonious 13-coloring of $G_{n,n}$<span data-label="fig:new_prism"></span>](h_flower_graph_6 "fig:"){width="90.00000%"}

\[b\]<span>0.3</span>

\[b\]<span>0.3</span>

\[b\]<span>0.3</span> ![ A harmonious 7-coloring of jewel graph $J_3$<span data-label="fig:jewel"></span>](h_book_4 "fig:"){width="70.00000%"}

\[b\]<span>0.3</span>

\[b\]<span>0.3</span>

### Cycle-related graphs with diameter greater than 2

Next we consider four cycle-related graphs with diameter greater than $2$.

1.  The *sunflower graph* $Sf_n$ is obtained from a $n$-wheel graph $W_n$ with set of vertices $\{v_0,v_1,v_2,\dots,v_n\}$ by adding $n$ vertices $u_i$, $1\leq i \leq n$, and joining each new vertex $u_i$ with two adjacent vertices $v_i$, $v_{i+1}$, $1\leq\ i \leq n-1$, and $u_n$ with $v_{n}$ and $v_1$. Thus, $Sf_n$ has $2n+1$ vertices, and $4n$ edges. The degree for each vertex of $Sf_n$: $d(v_0)=n$, $d(v_i)=5$, and $d(u_i)=2$, where $1 \leq i \leq n$.

    \[h\_sunflower\_graph\] The sunflower graph ${Sf}_n$ has $h(Sf_n)=7$, for $3 \leq n \leq 4$, $h(Sf_n)=8$ for $5 \leq n \leq 6$, and $h(Sf_n)=n+1$, for $n\geq 7$.

    \[b\]<span>0.3</span> ![A harmonious 8-coloring of $Sf_7$<span data-label="fig:sunflower_7"></span>](h_SunFlower_5 "fig:")

    \[b\]<span>0.3</span> ![A harmonious 8-coloring of $Sf_7$<span data-label="fig:sunflower_7"></span>](h_SunFlower_Sf6 "fig:")

    \[b\]<span>0.3</span> ![A harmonious 8-coloring of $Sf_7$<span data-label="fig:sunflower_7"></span>](h_SunFlower_Sf7 "fig:")

    The sunflower graph $Sf_3$ has diameter $2$, and thus, for Corollary \[cor:diameter\_2\], $h(Sf_3)=7$. For $4\le n\le 6$ we used our computer program described in proof of Theorem \[th12vf\] to obtain the harmonious chromatic number (see Figure \[fig:sunflower\_5\] and Figure \[fig:sunflower\_6\]).

    The sunflower graph $Sf_n$, with $n \geq 7$, has the harmonious chromatic number $h(Sf_n)\ge h(W_n)=n+1$. In order to prove that equality holds, we describe a harmonious coloring for $Sf_n$ with $n+1$ colors.

    Color the central vertex $v_0$ with color $1$; then color the vertices $v_i$, $1\leq i\leq n$, on the cycle with colors in order in set $C=\{2,3,\dots,{n+1}\}$, clockwise, and assign to the vertices $u_i$ colors in set $C$, clockwise, starting from the vertex $u_2$, situated at distance 3 from the vertex $v_1$ previously colored with $2$ (Figure \[fig:sunflower\_7\]).

2.  The *sun graph* $S_n$ is obtained from the complete graph $K_n$, with vertices denoted $v_1,v_2,\dots,v_n$ and $n$ new vertices $u_1,u_2,\dots,u_n$, each connected with two adjacent vertices on an outer cycle of $K_n$, more precisely vertex $u_i$ is adjacent with $v_i$ and $v_{i+1}$, for every $1\leq i\leq n-1$, and $u_n$ is adjacent with $v_n$ and $v_1$. Thus, the sun graph $S_n$ has $2n$ vertices, and $n(n-1)/2+2n$ edges.

    \[h\_sun\_graph\] The sun graph $S_n$, $n\ge 3$ has $h(S_n)=n+2$ if $n$ is even, and $h(S_n)=n+3$ if $n$ is odd.

    \[b\]<span>0.45</span> ![A harmonious 8-coloring of $S_6$ <span data-label="fig:sun_6"></span>](h_sun_5 "fig:")

    \[b\]<span>0.45</span> ![A harmonious 8-coloring of $S_6$ <span data-label="fig:sun_6"></span>](h_sun_6 "fig:")

    In a harmonious coloring of $S_n$ vertices $v_1,\ldots,v_n$ of the clique must have distinct colors. Denote these colors $1,\ldots,n$. Since $d(u_i,v_j)\le 2$ for every $1\le i,j\le n$, it follows that colors $1,\ldots,n$ cannot be used for vertices $u_1,\ldots, u_n$. Moreover, since $d(u_i,u_{i+1})=2$ for every $1\le i\le n-1$ and $d(u_n,u_1)=2$, it follows that, if $n$ is even at least $2$ new colors are needed for vertices $u_1,\ldots,u_n$ and if $n$ is odd at least $3$ new colors are needed. Hence $$h(S_n)\ge\left\{
    \begin{array}{ll} 
    n+2, &\mbox{if $n$ even}\\
    n+3, &\mbox{if $n$ odd.}\\
    \end{array}\right.$$ The lower bound can be achieved for the following coloring, hence equality holds:

    -   for $n$ even, let $c(v_i)=i$ for every $1\le i\le n$, $c(u_j)=n+1$ if $j$ is odd and $c(u_j)=n+2$ if $j$ is even for $1\le j\le n$ (Figure \[fig:sun\_6\]),

    -   for $n$ odd, let $c(v_i)=i$ for every $1\le i\le n$, $c(u_j)=n+1$ if $j$ is odd and $c(u_j)=n+2$ if $j$ is even for $1\le j\le n-1$ and $c(u_n)=n+3$ (Figure \[fig:sun\_5\]).

3.  The *closed sun graph* $\overline{\rm S_n}$ is the graph $S_n$ with edges between vertices $u_i, u_{i+1}$, where $1\leq i<n$, and between $u_n$ and $u_1$. Thus, $\overline{\rm S_n}$ has 2n vertices and $n(n-1)/2+3n$ edges. Then, $d(v_i)=n+1$, and $d(u_i)=4$.

    \[b\]<span>0.45</span> ![A harmonious 11-coloring of $\overline{\rm S_6}$ <span data-label="fig:closed_sun_6"></span>](h_closed_sun_5 "fig:")

    \[b\]<span>0.45</span> ![A harmonious 11-coloring of $\overline{\rm S_6}$ <span data-label="fig:closed_sun_6"></span>](h_closed_sun_6 "fig:")

    \[h\_closed\_sun\_graph\] The closed sun graph $\overline{\rm S_n}$ has $h(\overline{\rm S_n})=2n$, for $n\le 5$ and $h(\overline{\rm S_n})=n+h(C_n)$, for $n > 5$.

    For $n\le 5$ we have $h(\overline{\rm S_n})=2n$, since in this case $\overline{\rm S_n}$ has diameter $2$. For $n>5$, vertices of the clique must be colored with $n$ distinct colors and these colors cannot be used for any vertex from the outer cycle $C_n$, since a vertex from the outer cycle is at distance at most $2$ from any vertex of the clique; hence we have $h(\overline{\rm S_n})\ge n+h(C_n)$. To prove that equality holds, we consider the following coloring for $\overline{\rm S_n}$ (Figure \[fig:closed\_sun\_5\], Figure \[fig:closed\_sun\_6\]), which can be easily verified that is harmonious:

    -   first color with $1,\ldots,n$ the vertices of the clique $K_n$,

    -   then consider a harmonious coloring for the outer cycle $C_n$ with $h(C_n)$ colors, using colors from $n+1$ to $n+h(C_n)$.

4.  The *Lollipop graph* $L_{n,m}$

    Let $G$, $H$ be two connected graphs and consider one vertex from each of these two graphs: $a\in V(G)$, $b\in V(H)$. Denote by $(G,a) \odot (H,b)$ the graph obtained from the union of graphs $G$ and $H$ by identifying vertices $a$ and $b$. We will call this operation vertex-union.

    For two positive numbers $n\ge 3$, $m\ge 2$ *Lollipop graph* $L_{n,m}$ is the vertex-union $(K_n,u)\odot (P_m,v)$ where $u$ is any vertex of a clique $K_n$ and $v$ is a degree $1$ vertex of path $P_m$.

    ![A harmonious 8-coloring of lollipop graph $L_{6,4}$<span data-label="fig:lollipop"></span>](h_lollipop_C6_P4)

    \[h\_Lollipop\] Let $n\ge 3 $ and $m\ge 2$ and $t$ be the minimum natural number such that $m \le 1+nt+\frac{t(t-1)}{2}$. The Lollipop graph $L_{n,m}$ has the harmonious chromatic number $h(L_{n,m})=n+t$ in the following cases:

    -   $t$ is even and $n$ is odd

    -   $t$ and $n$ are even and $m \le 1+ nt+\frac{t(t-1)}{2} - \frac{t}{2}$

    -   $t$ is odd, $n$ is even and and $m\le 1+ nt+\frac{t(t-1)}{2} - (n-2)$

    -   $t$ and $n$ are odd and $m\le 1+ nt+\frac{t(t-1)}{2}-(n-2+\max({\frac{t-(n-2)}{2},0})))$

    otherwise $h(L_{n,m})=n+t+1$.

    In this proof for a complete graph $K_r$ we denote the vertices with $1,\ldots,r$. Also, for $n\le r$ we denote by $\left<[n]\right>$ the clique induced in $K_r$ by vertices $1,\ldots,n$.

    Let $k=nt+\frac{t(t-1)}{2}$.

    Let $r=h(L_{n,m})$ and let $c$ be an $r$-harmonious coloring of $L_{n,m}$. The $n$ vertices of the clique of $L_{n,m}$ must have distinct colors: assume w.l.o.g, that these colors are $1,\ldots,n$. Then, in the complete graph $K_r$, according to the coloring $c$, the colors of the vertices of the clique in $L_{n,m}$ correspond to a clique with $n$ vertices $1,\ldots,n$ in $K_r$ and the colors of the vertices from the path $P_m$ of $L_{n,m}$ correspond to a trail (possible closed) with $m$ vertices in $K_r-E(\left<[n]\right>)$ (obtained from $K_r$ by removing all the edges between vertices $1,\ldots,n$) starting with a vertex from $1,\ldots,n$.

    Conversely, if in a clique $K_r$ with $r\ge n$ there exists a trail with $m$ vertices in $K_r-E(\left<[n]\right>)$ starting with a vertex from $1,\ldots,n$ (assume w.l.o.g. it starts from vertex $1$), then $L_{n,m}$ has a $r$-harmonious coloring. It follows that the harmonious chromatic number of $L_{n,m}$ is the minimum $r$ with such property.

    Let $t$ be the smallest number such that $|E(L_{n,m})|=|E(K_n)|+|E(P_m)|\le E(K_{n+t})$, that is such $m-1\le nt+\frac{t(t-1)}{2}=k$. Then $h(L(K_{n,m}))\ge n+t$ and equality holds only if the following property is satisfied: there exists a trail with $m$ vertices in $K_{n+t}-E(\left<[n]\right>)$ starting with a vertex $1$.

    In $K_{n+t}-E(\left<[n]\right>)$ vertices $1,\ldots,n$ have degree $t$ and vertices $n+1,\ldots, n+t$ have degree $n+t-1$. In order to have a trail with $m$ vertices starting with vertex $1$ in $K_{n+t}-E(\left<[n]\right>)$, the largest subgraph of this graph that has an Eulerian trail must have at least $m-1$ edges and all vertices of this subgraph must have even degree with at most $2$ exceptions; if there are vertices of odd degree in this subgraph, then vertex $1$ must be one of them, thus at least $t-1$ of vertices $n+1,\ldots,n+t$ have even degree in this subgraph.

    We consider four cases, according to the parity of $n$ and $m$.

    1.  If $t$ is even and $n$ is odd, then $K_{n+t}-E(\left<[n]\right>)$ is Eulerian, hence it has an Eulerian cycle. This cycle includes a trail with $m$ vertices starting from vertex $1$, hence in this case $h(L(K_{n,m}))= n+t$.

    2.  If $t$ is even and $n$ is even, in order to have a subgraph in $K_{n+t}-E(\left<[n]\right>)$ with all vertices from $n+1$ to $n+t$ of even degree with at most one exception, then we must remove at least $\frac{t}{2}$ edges, hence $m-1$ must be at most $k-\frac{t}{2}$. We can obtain such a subgraph by removing edges $(n+1,n+2)$, $(n+3,n+4),\ldots, (n+t-1,n+t)$. This subgraph is Eulerian, hence is has a trail with $m$ vertices starting from vertex $1$. It follows that if $m-1\le k-\frac{t}{2}$, then we have $h(L(K_{n,m})= n+t$. Otherwise, $h(L(K_{n,m}))\ge n+t+1$ and equality holds, since by adding a new vertex to $K_{n+t}$ and joining it with $n+1,\ldots,n+t$ we obtain an Eulerian subgraph of $K_{n+t+1}-E(\left<[n]\right>)$ with at least $m$ edges.

    3.  If $t$ is odd and $n$ is even, then, in order to have a subgraph with an Eulerian trail, we must remove edges such that at least $n-2$ vertices from $1,\ldots,n$ have even degree. Since these vertices are pairwise nonadjacent, we must remove at least $n-2$ edges. For example if we remove $(3,n+1),(4,n+1),\ldots(n,n+1)$ we obtain a subgraph with an Eulerian trail with one extremity in $1$.

        Hence, in this case, if $m-1\le k-(n-2)$, then we have $h(L(K_{n,m}))= n+t$, otherwise, as in Case $2$, $h(L(K_{n,m}))= n+t+1$.

    4.  If $t$ is odd and $n$ is odd, consider two subcases.

        1.  If $t\ge n-2$, as in Case $2$, we must remove at least $\frac{n+t}{2}-1$ edges in order to have a subgraph with an Eulerian trail. We can remove the edges: $(i,n+i-2)$ for $3\le i\le n$, and $(n+n-1,n+n),(n+n+1,n+n+2),\ldots,(n+t-1,n+t)$ and obtain the desired subgraph, hence in this case if $m-1\le k-(\frac{n+t}{2}-1)=k-(n-2+\frac{t-n+2}{2})$ we have $h(L(K_{n,m}))= n+t$, otherwise, as in Case $2$, we have $h(L(K_{n,m}))= n+t+1$ .

        2.  If $t< n-2$, as in Case $3$, we must remove at least $n-2$ edges such that at least $n-2$ vertices from $1,\ldots,n$ became of even degree. For example, we remove the edges $(i,n+i-2)$ for $3\le i\le t+1$ and the edges $(i,n+t)$ for $t+2\le i\le n$ and obtain a subgraph with an Eulerian trail from vertex $1$. Hence, in this case, if $m-1\le k-(n-2)$, then we have $h(L(K_{n,m}))= n+t$, otherwise $h(L(K_{n,m})= n+t+1$.

Conclusions and future work {#sec:conclusions}
===========================

In this paper we studied the harmonious chromatic number, which is a proper vertex coloring such that for every two distinct colors $i$, $j$ at most one pair of adjacent vertices are colored with $i$ and $j$.

We showed that finding a minimum harmonious colorings for arbitrary graphs is APX-hard, the natural greedy algorithm is a $\Omega(\sqrt{n})$-approximation, and, moreover, we show a relationship between the minimum vertex cover and the harmonious chromatic number. In the second part of our paper we determined the exact value of the harmonious chromatic number for all $3$-regular planar graphs of diameter $3$, some non-planar regular graphs and cycle-related graphs.

We state an open problem related to the approximability of the harmonious chromatic number.

Does there exist a constant factor approximation algorithm for the harmonious chromatic number on arbitrary graphs?

Finally, we list a couple of classes of cycle-related graphs for which it is interesting to find the exact value of the harmonious chromatic number: square graph, tadpole or dragon graph, barbell graph, diamond snake, total graph of path, total graph of cycle.

{'source': 'arXiv_out/2106'}