# The Harmonious Coloring Game

Cláudia Linhares Sales, Thiago Marcilon, Nicolas Martins, Nicolas Nisse, Rudini Sampaio

► To cite this version:

Cláudia Linhares Sales, Thiago Marcilon, Nicolas Martins, Nicolas Nisse, Rudini Sampaio. The Harmonious Coloring Game. Information Processing Letters, 2026, 192, pp.106609. 10.1016/j.ipl.2025.106609. hal-05285890

HAL Id: hal-05285890

https://hal.science/hal-05285890v1

Submitted on 26 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Harmonious Coloring Game*

Cláudia Linhares Sales¹, Thiago Marcilon², Nicolas Martins³, Nicolas Nisse⁴, and
Rudini Sampaio¹

¹Dept. Computação, Univ. Federal do Ceará, Brazil

²Centro de Ciências e Tecnologia, Univ. Federal do Cariri, Brazil

³Inst. Engenharia e Desenvolv. Sustentável, UNILAB, Brazil

⁴Université Côte d'Azur, INRIA, CNRS, I3S, France

## Abstract

A harmonious *k*-coloring of a graph *G* is a 2-distance proper *k*-coloring of its vertices such that each edge is uniquely identified by the colors of its endpoints. Here, we introduce its game version: the harmonious coloring game. In this two-player game, Alice and Bob alternately select an uncolored vertex and assigns to it a color in {1, ..., *k*} with the constraint that, at every turn, the set of colored vertices induces a valid partial harmonious coloring. Alice wins if all vertices are colored; otherwise, Bob wins. The harmonious game chromatic number $χ_{hg}(G)$ is the minimum integer *k* such that Alice has a winning strategy with *k* colors. In this paper, we prove the PSPACE-hardness of three variants of this game. As a by-product, we prove that a variant introduced by Chen et al. in 1997 of the classical graph coloring game is PSPACE-hard even in graphs with diameter two. We also obtain lower and upper bounds for $χ_{hg}(G)$ in graph classes, such as paths, cycles, grids and forests of stars.

## 1 Introduction

A *k*-coloring of a graph *G* is a function *c* which associates to each vertex *v* a “color” *c*(*v*) ∈ {1, ..., *k*} in such a way that adjacent vertices have distinct colors. The *chromatic number* χ(*G*) is the minimum *k* such that *G* has a *k*-coloring. The *graph coloring game* is the game version of the coloring problem: given a graph *G* and a positive integer *k*, two players Alice and Bob alternate turns, starting with Alice, in selecting a non-colored vertex to be colored by a “color” in {1, ..., *k*} not already used in one of its neighbors. Alice wins if every vertex is successfully colored at the end; otherwise, Bob wins. The *game chromatic number* χg(*G*) is the minimum *k* such that Alice has a winning strategy. Clearly, χ(*G*) ≤ χg(*G*) ≤ Δ(*G*) + 1 where Δ(*G*) is the maximum degree of *G*.

The graph coloring game was introduced by Brams in the context of coloring maps and was described by Gardner in 1981 in his “Mathematical Games” column of Scientific American [14]. It remained unnoticed until Bodlaender [2] reinvented it in 1991 as the “Coloring Construction Game”, and its computational complexity was left as “an interesting open problem”.

After this, many papers were published investigating the graph coloring game and the game chromatic number [4, 7, 11, 16]. Only in 2020, it was finally proved that the graph coloring game (deciding if $χ_g(G) ≤ k$) is PSPACE-complete [6]. Thereafter, many games based on classical variants of the coloring problem were proved PSPACE-complete, such as the greedy coloring game [18] and the connected coloring game [19]. Online setting may also be seen as 2-Player games where one player reveals the vertices of a graph one after the other while the other player has to color them trying to minimize the number of colors. Online coloring games have been studied in [3, 17].

In this paper, we propose the game version of the harmonious coloring of a graph. A *harmonious k-coloring* of *G* is a *k*-coloring *c* of *G* such that {*c*(*u*), *c*(*v*)} ≠ {*c*(*x*), *c*(*y*)} for every two edges *uv* and *xy* of *G* [13]. That is, each edge is uniquely determined by the colors of its endpoints. The

<footnote>*Research supported by CNPq Project Tapioca 404479/2023-5, CAPES-Cofecub project Ma 1004/23, ANR projects P-GASE and EUR DS4H Investments in the Future ANR-17-EURE-0004, and by the Inria Associated Team CANOE.</footnote>
harmonious chromatic number $\chi_h(G)$ is the smallest $k$ such that $G$ admits a harmonious $k$-coloring. The computational complexity of determining the harmonious chromatic number was considered in [10] where it has been shown that the problem is already NP-complete in the class of forests of stars. General upper bounds on this parameter were provided in [9] and particular graph classes were considered such as paths, cycles [20, 15], bounded degree trees [8], etc. (e.g., see the recent work [12]).

In order to define the harmonious coloring game, we observe that a harmonious coloring is not only a proper coloring, but also a 2-distance proper coloring. That is, vertices at distance at most two must receive distinct colors. For example, in the path $P_3$ with vertices $v_1, v_2, v_3$, the vertices $v_1$ and $v_3$ must receive distinct colors, independently of the color of $v_2$, since otherwise the edges $v_1v_2$ and $v_2v_3$ will have the same colors in their endpoints.

We then say that a *partial coloring* of a graph is *harmonious* if there is no pair of colored vertices at distance at most two with the same color<fnref n="1" /> and there is no pair of edges whose endpoints are colored and the sets of colors of the endpoints are equal. With this, we can define the *harmonious coloring game* (HCG). Given a graph $G$ and a positive integer $k$, Alice and Bob (starting with Alice) alternately color uncolored vertices of $G$ in such a way that the partial coloring obtained in each turn is harmonious.

In other words, at each turn, the current player chooses an uncolored vertex $v$ and assigns to it a color $c(v) \in \{1, \dots, k\}$ such that: (a) there is no vertex colored $c(v)$ at distance at most two from $v$, and (b) there is no edge whose endpoints are already colored with colors $c(v)$ and $c(v')$ for every colored neighbor $v'$ of $v$.

Alice wins if every vertex is successfully colored at the end; otherwise, Bob wins. The *harmonious game chromatic number* $\chi_{hg}(G)$ is the least $k$ such that Alice wins the harmonious coloring game in $G$ with $k$ colors. Clearly, $\chi_h(G) \le \chi_{hg}(G)$.

**Our Contributions.** We start by focusing in Section 2 on the computational complexity of the harmonious coloring game, that is, the problem of deciding if $\chi_{hg}(G) \le k$. Although we were unable to prove that the original problem is PSPACE-complete, we were able to prove that three variants are. The first variant is related to a variant of the graph coloring game, named as *sequential coloring construction game* by Bodlaender [2] in 1981: the vertices must be colored following a predefined given sequence, with players only being able to choose the color to be used. Bodlaender proved that this variant is PSPACE-complete [2] and we use this fact to prove in Section 2 that the *sequential harmonious coloring game* is also PSPACE-complete even for split graphs. Roughly, given a graph $G$, a new graph $G'$ is obtained by subdividing once each edge of $G$ and turning the new vertices (one vertex per edge of $G$) into a clique. Then, in $G'$, if the vertices of the clique (corresponding to edges of $G$) are colored first, then the coloring of the remaining vertices (the “original” vertices of $G$) must correspond to a proper coloring of $G$.

The second variant considers that some vertices of the input graph are pre-colored before the beginning of the game. We then prove that the *pre-colored harmonious coloring game* is PSPACE-complete even for split graphs in which the pre-colored vertices induce a maximum clique. The third variant is related to another variant of the graph coloring game, named as *Chromatic Game II* by Chen [5] in 1997, in which Bob can color a vertex $v$ with a new color (that was not used previously) only if $v$ cannot be colored with an already used color. Although this game was introduced almost thirty years ago, to the best of our knowledge, it was not proved PSPACE-hard before. We then prove that the Chromatic Game II is PSPACE-complete and use this to prove that the corresponding variant of the harmonious coloring game is also PSPACE-complete.

In Section 3, we obtain lower and upper bounds for general graphs. For instance, it is clear that $\chi_{hg}(G) \ge \Delta(G)+1$ since, by definition, all vertices in the closed neighborhood of a vertex must receive distinct colors, where $\Delta(G)$ is the maximum degree of $G$. On the other hand, if the number of available colors is large compared with the maximum size of the close neighborhood at distance 2, this may help Alice. In Section 4, we obtain for paths and cycles the lower bound $4\left\lfloor\frac{n}{12}\right\rfloor + 1$ and the upper bound $\frac{2(n+3)}{3}$ for the harmonious game chromatic number. In Section 5, we use our results in paths to obtain lower and upper bounds for the Cartesian grid, the triangular grid and the king grid. The lower bounds rely on the fact that, in an “induced” path, Bob may create a “large” (linear in the size of the path) monochromatic set, forcing all the neighbors of this set to receive distinct colors. Finally, motivated by

<footnote n="1">¹The reason for adding this constraint is that, without it, a simple winning strategy for Bob (in any connected graph with diameter at least two) would be to color a vertex at distance two from the first vertex colored by Alice, with the same color.</footnote>
the fact that computing the harmonious chromatic number of forests of stars in NP-complete [10], we give, in Section 6, lower and upper bounds for the harmonious game chromatic number in this graph class. We conclude with some open problems.

# 2 PSPACE-hardness of three variants

## 2.1 Sequential variant and Pre-colored variant

When Bodlaender first introduced the graph coloring game, he also defined a sequential version of the problem that he called *Sequential Coloring Construction Game* [2]. In this variant, the instance is a graph $G$, a positive integer $k$ and an ordering $(v_1, v_2, \dots, v_n)$ of the vertices of $G$. Alice and Bob alternate color the vertices of $G$ in such a way that, on turn $i$, the current player (Alice if $i$ is odd and Bob if $i$ is even) must color the vertex $v_i$ with a color in $\{1, \dots, k\}$ distinct from the ones appearing on its neighborhood. As usual, Alice wins if all the vertices of $G$ are colored, and Bob wins otherwise. The goal is to decide whether Alice has a winning strategy. Bodlaender [2] proved that this problem is PSPACE-complete even for $k = 3$.

Here we introduce the sequential harmonious coloring game similarly except that the coloring constructed by Alice and Bob must always induce a harmonious partial coloring of $G$. The next theorem proves PSPACE-hardness even for split graphs, which are graphs whose vertex set has a partition $(K, S)$, where $K$ induces a clique and $S$ is an independent set.

**Theorem 1.** Deciding if Alice wins the sequential harmonious coloring game is PSPACE-complete even when the input graph is a split graph with partition $(K, S)$ and $k = |K| + 3$.

*Proof.* The problem is clearly in PSPACE. We obtain a reduction from the sequential coloring construction game, which is PSPACE-complete [2]. Given a graph $G = (V, E)$, let $\hat{G}$ be the graph obtained from $G$ by subdividing each edge exactly once and adding an edge between each pair of new vertices. Note that $\hat{G}$ is a split graph with partition $(K_{|E|}, V)$, such that each vertex of the clique is adjacent to exactly 2 vertices of the independent set. This construction was proposed previously in [1] to prove that deciding if $\chi_h(G) \le k$ is NP-complete for split graphs.

Let $\mathcal{I}$ be an instance of the sequential coloring construction game in a graph $G = (V, E)$ with ordering $(v_1, v_2, v_3, \dots, v_n)$ and $k = 3$ colors. We assume that $G$ has an even number of edges. If this is not the case, one can add an isolated edge to $G$ and append both of its endpoints to the end of the ordering without changing the outcome of $\mathcal{I}$.

We claim that Alice has a winning strategy for the sequential harmonious coloring game on $\hat{G}$ with ordering $(e_1, e_2, e_3, \dots, e_{|E|}, v_1, v_2, v_3, \dots, v_n)$ with $|E| + 3$ colors if and only if she also has a winning strategy on $\mathcal{I}$, where $e_1, e_2, e_3, \dots, e_{|E|}$ is any ordering of the vertices in the clique $K_{|E|}$.

Suppose that Alice has a winning strategy on $\mathcal{I}$. When playing the sequential harmonious coloring game on $\hat{G}$, for the first $|E|$ turns each player has to color his/her vertex using a new color, since $\{e_1, \dots, e_{|E|}\}$ is a clique in $\hat{G}$. In turn $|E| + 1$, Alice starts coloring $v_1$ (recall that $E$ is even) and use the same strategy of the sequential coloring construction game to color the remaining vertices with the 3 remaining colors.

That is possible because, given that the clique is already completely colored, no vertex $v_i$ can receive a color already used in any vertex $e_j$ of the clique, since they are at distance at most 2. Furthermore, if a pair of vertices $v_i$ and $v_j$ are adjacent in $G$, they share a common neighbor in $\hat{G}$, namely the vertex resulting of the subdivision of the edge with endpoints $v_i$ and $v_j$, and must receive distinct colors on a harmonious coloring of $\hat{G}$. Since these are the only restrictions when coloring the vertices of the independent set of $\hat{G}$, Alice and Bob can make exactly the same moves as if they were playing on $\mathcal{I}$.

The same arguments of the last two paragraphs can be applied in the case when Bob has a winning strategy on $\mathcal{I}$. Thus, in that case, Bob also wins when playing the sequential harmonious coloring game on $\hat{G}$ with ordering $(e_1, e_2, e_3, \dots, e_{|E|}, v_1, v_2, v_3, \dots, v_n)$ with $|E| + 3$ colors. $\square$

In the proof of Theorem 1, note that it is not necessary to have an ordering among the vertices of the clique. In fact, since the coloring game, without the ordering, has been proven PSPACE-complete [6], we could use the same arguments, just requiring that the vertices of the clique are pre-colored at the beginning of the game, to prove that the harmonious coloring game is also PSPACE-complete when some vertices are pre-colored.
**Theorem 2.** *Given a split graph G with a pre-coloring of the vertices of its clique and a positive integer k, deciding if Alice has a winning strategy for the harmonious coloring game on G with k colors is PSPACE-complete.*

## 2.2 Bob restricted variant

In 1997, Chen et al. [5] introduced a new variation of the classical graph coloring game, that they called Chromatic Game II. This version is played exactly the same way except that, in each turn, Bob can color a vertex $v$ with a new color (that was not used previously) only if $v$ cannot be colored with an already used color. The minimum number of colors for which Alice has a winning strategy on a graph $G$ in this variation of the game is denoted by $\chi_g^*(G)$. Clearly $\chi(G) \le \chi_g^*(G) \le \chi_g(G)$ since Bob has more constraints.

Although this variant was introduced almost thirty years ago, to the best of our knowledge, it was not proved PSPACE-hard before. The next theorem obtains this result for disconnected graphs and the next corollary proves for graphs with diameter two. Later we use these facts to prove the PSPACE-hardness of the corresponding variant of the harmonious coloring game.

**Theorem 3.** *The Chromatic Game II is PSPACE-complete even in disconnected graphs with an odd number of vertices. That is, given a graph $G$ and an integer $k$, deciding if $\chi_g^*(G) \le k$ is PSPACE-complete.*

*Proof.* The problem is clearly in PSPACE. We obtain a reduction from the graph coloring game, which was proved PSPACE-complete in [6]. Let $(H, k)$ be an instance of the graph coloring game. The reduction of [6] is from the POSCNF logical game and the constructed graph there can be made with an even or an odd number of vertices, as desired, just including new variables that are not used in the formula. So, we assume that $H$ has an odd number of vertices.

Let $r = \lfloor \frac{k+1}{2} \rfloor$ and $s = \lfloor \frac{k+1}{2} \rfloor$ and then $r+s = k+1$. Let $Q_k$ be the graph with four cliques $A, B, C$ and $D$ with $r, s, r$ and $s$ vertices, respectively, with all edges between $A$ and $B$, between $B$ and $C$ and between $C$ and $D$. Let $AB = A \cup B, BC = B \cup C$ and $CD = C \cup D$. See Figure 1. Notice that $AB, BC$ and $CD$ are cliques with $k+1$ vertices. Note that, if $a_i \in A$ and $d_j \in D$ have the same color in the graph $Q_k$, then their color cannot be used in $BC$ and therefore more than $k+1$ colors will be needed to color $Q_k$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Graphs $Q_3, Q_4$ and $Q_5$. In $Q_k$, the sets $A$ and $C$ contains $r$ vertices, and $B$ and $D$ contains $s$ vertices, where $r = \lfloor \frac{k+1}{2} \rfloor$ and $s = \lfloor \frac{k+1}{2} \rfloor$. Moreover, $AB, BC$ and $CD$ have $k+1$ vertices each.</figcaption></figure>

Let $H'$ be the graph obtained from $H$ by adding a vertex $u_1$ adjacent to every vertex of $H$ and an isolated vertex $u_2$. Note that $|V(H')|$ is odd. We construct the instance $(G, k+1)$ of the Chromatic Game II, where $G$ is obtained from the disjoint union of $H'$ and $Q_k$. See Figure 2. Notice that $G$ is disconnected. We prove that Alice has a winning strategy in the graph coloring game with $k$ colors in $H$ if and only if she also has in the Chromatic Game II with $k+1$ colors in $G$. This implies that $\chi_g(H) = k$ if and only if $\chi_g^*(G) = k+1$.

**Claim 1.** *Consider the Chromatic Game II in $G$ with $k+1$ colors. Alice can always maintain $Q_k$ in such a way that the colors in $A$ (resp. $B$) are the same as in $C$ (resp. $D$).*
<figure><img src="image_3.png" /><figcaption>Figure 2: Graph $G$ obtained from $(H, k)$ in the reduction of Theorem 3. Recall that $A, B, C$ and $D$ are cliques with $r, s, r$ and $s$ vertices, respectively, where $r = \lfloor \frac{k+1}{2} \rfloor$ and $s = \lfloor \frac{k+1}{2} \rfloor$, and that $AB, BC$ and $CD$ are cliques with $k+1$ vertices each.</figcaption></figure>

*Proof of Claim.* Since $|V(H')|$ is odd, Alice can play in $Q_k$ only in response to moves of Bob in $Q_k$. If Bob colors a vertex of $A$ (resp. $C$), Alice colors a vertex of $C$ (resp. $A$) with the same color. If Bob colors a vertex of $B$ (resp. $D$), Alice colors a vertex of $D$ (resp. $B$) with the same color. $\diamond$

We say that $Q_k$ is in Phase 1 if less than $k$ colors are used in $Q_k$, the colors in $A$ (resp. $B$) are the same as in $C$ (resp. $D$) and the number of colored vertices in $A$ are the same as in $B$. We say that $Q_k$ is in Phase 2 if exactly $k$ colors are used in $Q_k$ and exactly two vertices of $Q_k$ are uncolored. We say that $Q_k$ is in Phase 3 if more than $k$ colors are used in $Q_k$. Notice that, in Phase 1, $A, B, C$ and $D$ have at least one uncolored vertex each and the number of colors in $Q_k$ is even (since no color in $A$ can appear in $B$, and vice versa). Moreover, the game starts with $Q_k$ in Phase 1.

**Claim 2.** *Consider the Chromatic Game II in $G$ with $k+1$ colors and suppose that $Q_k$ is in Phase 1. If Bob is the next to color a vertex in $Q_k$, he can force an alternating sequence of moves in the vertices of $Q_k$, taking it to Phase 2 or 3, in such a way that, if Alice does not follow this sequence, she loses.*

*Proof of Claim.* Suppose that $Q_k$ is in Phase 1 and Bob is the next to play in $Q_k$. Bob can repeat the following procedure until $Q_k$ is in Phase 2 or Phase 3:

(i) he colors a vertex of $A$ with a color $x_1$. If Alice colors a vertex of $D$ with color $x_1$, she loses (since $x_1$ cannot be used in $BC$). If she colors a vertex of $D$ with color $y_1 \neq x_1$ and $k+1$ colors are used in $Q_k$, then $Q_k$ is in Phase 3. If she colors a vertex of $D$ with color $y_1 \neq x_1$ and less than $k+1$ colors are used in $Q_k$, then Bob colors a vertex of $A$ with $y_1$ and wins (since $y_1$ cannot be used in $BC$). So, we may assume that Alice colors a vertex of $C$ with color $x_1$, since otherwise Bob colors a vertex of $D$ with $x_1$ and wins (since $x_1$ cannot be used in $BC$);

(ii) After that, if $Q_k$ is not in Phase 2 nor Phase 3, Bob colors a vertex of $D$ with a color $x_2$. If Alice colors a vertex of $A$ with color $x_2$, she loses (since $x_2$ cannot be used in $BC$). If she colors a vertex of $A$ with color $y_2 \neq x_2$ and $k+1$ colors are used in $Q_k$, then $Q_k$ is in Phase 3. If she colors a vertex of $A$ with color $y_2 \neq x_2$ and less than $k+1$ colors are used in $Q_k$, then Bob colors a vertex of $D$ with $y_2$ and wins (since $y_2$ cannot be used in $BC$). So, we may assume that Alice colors a vertex of $B$ with color $x_2$, since otherwise Bob colors a vertex of $A$ with $x_2$ and wins (since $x_2$ cannot be used in $BC$). With this, $Q_k$ is in Phase 1 or Phase 2.

$\diamond$

**Claim 3.** *Consider the Chromatic Game II in $G$ with $k+1$ colors and suppose that $Q_k$ is in Phase 1. If Alice is the next to color a vertex in $Q_k$, then either Alice loses or Bob can take $Q_k$ to Phase 1 or Phase 2.*

*Proof of Claim.* Suppose that $Q_k$ is in Phase 1 and Alice is the next to play in $Q_k$. Recall that $A, B, C$ and $D$ have at least one uncolored vertex each before Alice's move. If Alice colors a vertex of $A$ (resp. $D$), Bob colors a vertex of $D$ (resp. $A$) with the same color, winning the game, since this color cannot be used in $BC$. So, without loss of generality, suppose that Alice colors a vertex of $B$ with
color $x$. If $k$ colors are used in $Q_k$ after Alice's move, then Bob colors a vertex of $D$ with the same color $x$, taking $Q_k$ to Phase 2.

So assume that less than $k$ colors are used in $Q_k$ after Alice's move. Then Bob colors a vertex of $A$ with a color $y \neq x$. If Alice colors a vertex of $C$ with $y$, then Bob colors a vertex of $D$ with $x$, taking $Q_k$ to Phase 1 or Phase 2. If Alice colors a vertex of $D$ with $y$, then this color cannot be used in $BC$ and Bob wins. If Alice does not color a vertex of $C$ with $y$ and $D$ has at least one uncolored vertex after Alice's move, then Bob colors a vertex of $D$ with $y$, winning the game since $y$ cannot be used in $BC$. If Alice colors the last uncolored vertex of $D$ with a color $z \neq x$, then $x$ cannot be used in $CD$ and Alice loses. If Alice colors the last uncolored vertex of $D$ with color $x$, then Bob colors a vertex of $C$ with $y$, taking $Q_k$ to Phase 1 or Phase 2. In all these cases, either Alice loses or Bob takes $Q_k$ to Phase 1 or Phase 2 using a color $y$ that was not used before in $Q_k$. $\diamond$

First suppose that Alice wins the graph coloring game on $H$ using $k$ colors. Let us describe a winning strategy for her on $G$ on the Chromatic Game II with $k+1$ colors. Alice starts coloring a vertex of $H$ using her winning strategy (for the graph coloring game). If Bob colors a vertex of $H$, Alice follows her winning strategy on $H$. If Bob colors a vertex of $Q_k$ and there are more than two uncolored vertices in $Q_k$, Alice colors a vertex of $Q_k$, ensuring from Claim 1 that at most $k$ colors are used in $Q_k$ (for now). If Bob colors $u_1$, Alice colors $u_2$. If Bob colors $u_2$ and $u_1$ is not colored, Alice colors $u_1$. If Bob colors the penultimate uncolored vertex of $Q_k$ and $u_1$ is not colored, then Alice colors $u_1$ (notice that, in this case, there are $k+1$ colors in $Q_k$ and Bob cannot force a new color in the last uncolored vertex of $Q_k$). In this case, we pair $u_2$ and the last uncolored vertex of $Q_k$ (that is, if Bob colors one of them, Alice colors the other). If Bob colors the penultimate uncolored vertex of $Q_k$ and $u_1$ is colored (and then $u_2$ is also colored), Alice colors the last uncolored vertex of $Q_k$ with the same color. Since $Q_k$ has an even number of vertices, Alice ensures an alternating sequence of moves in $H$, that is, no player makes two consecutive moves in $H$. Moreover, since $|V(H)|$ is odd, Alice ensures that Bob is always the first to play outside $H$ after any sequence of moves in $H$. Finally notice that, when Bob forces $k+1$ colors in $Q_k$ (and such a color can now be used in $H'$), Alice ensures that $u_1$ is colored and then only $k$ colors can be used in $H$. With this, Alice ensures at most $k+1$ colors in $Q_k$ and at most $k+1$ colors in $H'$, winning the Chromatic Game II on $G$.

Now suppose that Bob wins the graph coloring game on $H$ with $k$ colors. Let us describe a winning strategy for him on $G$ on the Chromatic Game II with $k+1$ colors. If Alice colors $u_1$ (resp. $u_2$), Bob colors $u_2$ (resp. $u_1$). If $Q_k$ is in Phase 1 and Alice colors a vertex in $Q_k$, Bob can take $Q_k$ to Phase 1 or Phase 2 from Claim 3. If Alice colors the penultimate uncolored vertex of $Q_k$ (Phase 3), Bob colors the last uncolored vertex of $Q_k$. If $Q_k$ is in Phase 2 or 3 and Alice colors a vertex of $H$, then Bob colors a vertex in $H$ following his winning strategy on $H$ with $k$ colors. If $Q_k$ is in Phase 1 and Alice colors a vertex of $H$, then Bob can force from Claim 2 a sequence of moves using $k$ colors in $Q_k$ taking $Q_k$ to Phase 2 or 3. After that, Bob colors a vertex in $H$ following his winning strategy on $H$ with $k$ colors. Since $Q_k$ has an even number of vertices, Bob ensures an alternating sequence of moves in $H$, that is, no player makes two consecutive moves in $H$. With this, Bob obtains a vertex of $H'$ that cannot be colored in the Chromatic Game II on $G$ with $k+1$ colors and wins. $\square$

**Corollary 1.** *The Chromatic Game II is PSPACE-complete even in connected graphs of diameter two.*

*Proof.* Theorem 3 proved that the Chromatic Game II is PSPACE-complete even in disconnected graphs with an odd number of vertices. We will prove that the same is valid for connected graphs with diameter two. Let $(G, \ell)$ be an instance of the Chromatic Game II such that $G$ is disconnected and $|V(G)|$ is odd. We obtain an instance $(G', \ell+1)$ of the Chromatic Game II, where $G'$ has diameter two, such that $\chi_g^*(G) = \ell$ if and only if $\chi_g^*(G') = \ell+1$. The graph $G'$ is obtained from $G$ by adding two vertices $w_1$ and $w_2$ adjacent to every vertex of $G$. Notice that $G'$ has diameter two.

First suppose that Alice has a winning strategy in $G$ with $\ell$ colors. We describe a winning strategy for her in $G'$ with $\ell+1$ colors. Alice starts coloring a vertex of $G$ following her winning strategy on $G$. If Bob colors a vertex of $G$, Alice follows her winning strategy on $G$. Since $|V(G)|$ is odd, Alice ensures that Bob is the first to play outside $G$ in the game on $G'$. If Bob colors $w_1$ (resp. $w_2$), Alice colors $w_2$ (resp. $w_1$) with the same color. Since Alice ensures $\ell$ colors in $G$ and just one new color in both $w_1$ and $w_2$, we are done (recall that Bob can only use a new color when there is no other color available). Analogously if Bob has a winning strategy in $G$ with $\ell$ colors. $\square$
Motivated by this variant by Chen et al. [5] of the graph coloring game, we introduce the *Restricted Harmonious Coloring Game* (HCG*). This variant of the game plays exactly as the harmonious coloring game except that Bob can color a vertex $v$ with a new color (that was not used previously) only if $v$ cannot be colored with an already used color. The minimum number of colors for which Alice has a winning strategy on a graph $G$ on HCG* is denoted by $\chi_{hg}^*(G)$. Clearly, $\chi_h(G) \le \chi_{hg}^*(G) \le \chi_{hg}(G)$. We remark that the results of the upcoming Lemma 2 and Theorems 5, 6 and 7 also hold for $\chi_{hg}^*(G)$, since Bob's strategy to achieve the lower bounds is to use the same color repeatedly.

We use Theorem 3 to prove that this version of the harmonious coloring game is also PSPACE-complete even for split graphs.

**Theorem 4.** *The Restricted Harmonious Coloring Game HCG*\* is PSPACE-complete even in split graphs. That is, given a split graph $G$ and an integer $k$, deciding if $\chi_{hg}^*(G) \le k$ is PSPACE-complete.

*Proof.* The problem is clearly in PSPACE. We obtain a reduction from the Chromatic Game II, which was proved PSPACE-hard in Theorem 3. Let $G = (V, E)$ and $k$ be an instance of Chromatic Game II. Let $\hat{G}$ be the split graph obtained from $G$ as in the proof of Theorem 1 (subdividing each edge exactly once and adding an edge between each pair of new vertices). Again, we can assume that $|E|$ is even. We prove that Alice has a winning strategy in the Chromatic Game II on $G$ with $k$ colors if and only if she also has in HCG\* on $\hat{G}$ with $k + |E|$ colors.

Let $C$ be the clique of $\hat{G}$ with the new vertices. Notice that every color of a vertex $v$ of $C$ is used only once, since every vertex of $\hat{G}$ is at distance at most 2 from $v$.

If a vertex $v \in V$ is colored, then its color cannot be used in any vertex of the clique $C$ and any $u \in N_G(v)$ since $v$ and $u$ have a common neighbor in $C$ (the new vertex corresponding to their edge). Therefore, the partial coloring after each move must induce a coloring of $G$.

Furthermore, if Bob can color a vertex $v \in V$ with a new color $c$, it means that for every color $a$ already used on a vertex of $V$ there is an edge with endpoints colored $a$ and $b$ for some color $b$ appearing in the neighborhood of $v$ in $\hat{G}$. Since the neighborhood of $v$ is composed only by the vertices of the clique, which have a unique color each, that means that for every color $a$ already used in the vertices of $V$ there is a vertex $u \in N_G(v)$ with color $a$. Therefore Bob is restricted when he colors a vertex of $V$ in the HCG\* on $\hat{G}$ in the exact same fashion he is on the Chromatic Game II on $G$.

If Alice has a winning strategy for the Chromatic Game II on $G$ with $k$ colors, then, to win in HCG\* on $\hat{G}$ with $k + |E|$ colors, she always colors a vertex of $G$ following her winning strategy on it, unless Bob just colored a vertex of the clique $C$ on his last turn, which, in this case, Alice just colors another vertex of the clique. Consequently, Alice never allows Bob to “pass” his turn in $G$.

The case in which Bob has a winning strategy for the Chromatic Game II on $G$ with $k$ colors is analogous to the one in the previous paragraph, except that it is Bob that uses his winning strategy to color the vertices of $V$. $\square$

## 3 General bounds

In this section, we provide some useful bounds and lemmas on $\chi_{hg}(G)$ in general graphs $G$.

**Fact.** $\chi_{hg}(G) \le n$ for every graph $G$ with $n$ vertices.

*Proof.* At her turn, Alice may always use the smallest unused color (i.e., a new color). $\square$

We say that Alice plays *greedily* if, at her turn, she can choose an arbitrary uncolored vertex and colors it with any possible (i.e., satisfying the constraints of the game) color.

We will often use the following easy result for the lower bounds.

**Lemma 1.** *If, at the end of a game, there exists a monochromatic set $X$ of vertices and all vertices in $N(X)$ have been colored, then at least $|N(X)| + 1$ colors have been used.*

Next we obtain an upper bound on $\chi_{hg}$ in general graphs with bounded maximum degree. This result will be used later in particular graph classes.

**Lemma 2.** Let $y \ge \max\left\{\frac{\Delta \cdot (n+\Delta+1)}{\Delta+1}, \Delta \cdot (\Delta - 1) + 1\right\}$. Then Alice *greedily* wins the harmonious coloring game with $y$ colors in a graph $G$ with $n$ vertices and maximum degree $\Delta$.
*Proof.* Alice plays greedily until she cannot play anymore. We show that actually all vertices have been colored. By contradiction, suppose that Alice loses. Let $Y$ be the set of colored vertices after the end of the game. Then $|Y| < n$, since some vertices remain uncolored and cannot receive any available color.

Let $v$ be an uncolored vertex. If there are no colored vertices in $N(v)$, then the set of colors forbidden to $v$ are exactly the ones used at distance 2 from $v$. Since $y \ge \Delta(\Delta - 1) + 1$, there's at least one color available for $v$, a contradiction.

Otherwise, let $C \neq \emptyset$ be the set of colors received by the neighbors of $v$. Let $X \subseteq V(G)$ be the set of all vertices colored with a color in $C$. Since $v$ cannot be colored, for each color $c \notin C$, there must be a vertex colored with $c$ adjacent to a vertex of $X$. Note that there are at least $y - |C| \ge y - \Delta$ such colors $c$ and so $|N(X)| \ge y - \Delta$. Since the vertices in $X$ have degree at most $\Delta$, then $|X| \ge \frac{y-\Delta}{\Delta}$. Furthermore, each color not appearing on $N(v)$ was used at least once. Hence, we obtain a contradiction:

$$|Y| \ge |N(X)| + |X| \ge y - \Delta + \frac{y - \Delta}{\Delta} = \frac{(\Delta + 1)(y - \Delta)}{\Delta} \ge \frac{(\Delta + 1)(\frac{\Delta(n+\Delta+1)}{\Delta+1} - \Delta)}{\Delta} = n.$$

□

**Corollary 2.** Let $G$ be any $n$-node graph with maximum degree $\Delta$, then

$$\chi_{hg}(G) \le \max \left\{ \frac{(n + \Delta + 1)\Delta}{\Delta + 1}, (\Delta - 1)\Delta + 1 \right\}.$$

# 4 Paths and cycles

Let $P_n$ and $C_n$ be the path and the cycle with $n$ vertices, respectively.

**Lemma 3.** $\chi_{hg}(P_n) \ge 4 \lfloor \frac{n}{12} \rfloor + 1$

*Proof.* The strategy for Bob is to create a color class with size at least $2 \lfloor \frac{n}{12} \rfloor$. Indeed, assume that Bob manages to create a monochromatic set $X$ of size at least $2 \lfloor \frac{n}{12} \rfloor$. By Lemma 1, at least $|N(X)| + 1$ colors are used. Below, we show how Bob creates such a set $\tilde{X}$ with all vertices with degree two, leading to the use of at least $4 \lfloor \frac{n}{12} \rfloor + 1$ colors.

Let $P_n = (u_1, u_2, \dots, u_n)$. Assume, for simplicity's sake, that $n$ is divisible by 12 and let $P^i = (v_1^i, v_2^i, \dots, v_{12}^i)$ be the $i$-th subpath of order 12 of $P_n$, with $1 \le i \le \frac{n}{12}$, that is $v_k^i = u_{12(i-1)+k}$. Bob's strategy is the following (note that Bob colors a vertex of some subpath $P^i$ if and only if Alice has just colored a vertex of $P^i$):

i) If Alice plays on $P^i$ for the first time on some vertex $v_j^i$ with color $c \neq 1$, then Bob colors $v_{j-2}^i$ with color 1 if he can do so and $j-2 > 1$. Otherwise, Bob colors $v_{j+2}^i$ with color 1.

ii) If Alice plays on $P^i$ for the first time on some vertex $v_j^i$ with color $c = 1$, then Bob colors $v_{j-3}^i$ with color 1 if he can do so and $j-3 > 1$. Otherwise, Bob colors $v_{j+3}^i$ with color 1.

iii) If Alice plays on some $P^i$ that already has colored vertices, then Bob colors any vertex $v \in V(P^i) \setminus \{v_1^i, v_{12}^i\}$ with color 1 if he can do so. Otherwise, Bob colors any uncolored vertex $v \in V(P^i)$ with a color $c \neq 1$.

iv) If Alice plays on some $P^i$, the only vertex left to color on $P^i$ is $v \in \{v_1^i, v_{12}^i\}$ and the only color available for $v$ is 1, then Bob colors $v$ with 1.

**Claim 4.** If, at the end of the game, $c(v_{12}^{i-1}) \neq 1$ and $c(v_1^{i+1}) \neq 1$ then, after Bob's second move in $P^i$, there are at least 2 vertices with color 1 in $V(P^i) \setminus \{v_1^i, v_{12}^i\}$.

*Proof of Claim.* Observe that initially, since $c(v_{12}^{i-1}) \neq 1$ and $c(v_1^{i+1}) \neq 1$, all 10 vertices in $V(P^i) \setminus \{v_1^i, v_{12}^i\}$ can receive color 1.

If Alice's first move on $P^i$ is to color a non-extremity vertex of $P^i$ with color 1, Bob will apply rule (ii) and we are done.

If Alice's first move on $P^i$ is to color a vertex $x$ with a color $c \neq 1$ she forbids color 1 for at most 3 vertices ($x$ and its neighbors) in $V(P^i) \setminus \{v_1^i, v_{12}^i\}$. Furthermore, after Bob applies rule i) (let $z$ be the
vertex he colored 1), he forbids color 1 for at most 3 more vertices (z, the neighbor y of z that is not a neighbor of x and the other neighbor of y) in $V(P^i) \setminus \{v_1^i, v_{12}^i\}$. After that, on Alice second move in $P^i$ if she colors a non-extremity vertex of $P^i$ with color 1 we are done. If she colors a vertex with a color distinct from 1 she forbids at most 3 more vertices from receiving color 1 in $V(P^i) \setminus \{v_1^i, v_{12}^i\}$, therefore there is at least one vertex that can still receive color 1 and it will receive this color after Bob applies rule iii).

Now suppose that Alice colors $v_1^i$ (resp., $v_{12}^i$) with color 1 in her first move in $P^i$. Then, in his first move on $P^i$, Bob will color $v_4^i$ (resp., $v_9^i$) and on his second move either Alice will color a vertex in $V(P^i) \setminus \{v_1^i, v_{12}^i\}$ with color 1 or, after her move, there will be at least one vertex that can be colored with 1 in $V(P^i) \setminus \{v_1^i, v_{12}^i\}$ (even if Alice colored the other extremity of $P^i$ with color 1). If the later is true then Bob applies rule iii) on his second move in $P^i$ and colors such vertex with 1. The argument is analogous if we assume that Alice colors a extremity of the path with 1 only on her second move on $P^i$.

Therefore, at the end of the game, for each $P^i$ such that $c(v_{12}^{i-1}) \neq 1$ and $c(v_1^{i+1}) \neq 1$, there are at least 2 vertices with color 1 in $V(P^i) \setminus \{v_1^i, v_{12}^i\}$. ◇

Observe that, in the case $c(v_{12}^{i-1}) \neq 1$ and $c(v_1^{i+1}) \neq 1$, if Alice or Bob colors either $v_1^i$ or $v_{12}^i$ with color 1, then $P^i$ will have at least 3 vertices colored 1. If Alice and Bob color both $v_1^i$ and $v_{12}^i$ with color 1, then $P^i$ will have exactly 4 vertices colored 1.

**Claim 5.** If, at the end of the game, $c(v_{12}^{i-1}) = 1$ or $c(v_1^{i+1}) = 1$, then after Bob first move in $P^i$, there is at least 1 vertex colored 1 in $V(P^i) \setminus \{v_1^i, v_{12}^i\}$.

*Proof of Claim.* Assume that, in her first move on $P^i$, Alice colors a vertex v with color 1. If $v \neq v_{12}^i$ and $v \neq v_1^i$ we are done. Otherwise, Alice's move forbids color 1 either for the vertices $v_{11}^i$ and $v_{10}^i$ or $v_2^i$ and $v_3^i$. After that Bob, will apply rule ii) and color $v_9^i$ with color 1 in the first case or color $v_4^i$ with color 1 on the second case.

If in her first move on $P^i$ Alice colors a vertex $v_j^i$ with a color $c \neq 1$, she forbids color 1 for at most 3 vertices on $V(P^i) \setminus \{v_1^i, v_{12}^i\}$. After that, Bob certainly can apply rule i) and color $v_{j-2}^i$ or $v_{j+2}^i$ with color 1. ◇

Let $c_1(P^i)$ denote the number of vertices with color 1 in $P^i$ at the end of the game. From both claims, by the end of the game, for each $1 \le i \le \frac{n}{12}$, either $c_1(P^i) \ge 2$ or $(c_1(P^i) = 1$ and $(c(v_{12}^{i-1}) = 1$ or $c(v_1^{i+1}) = 1))$.

Assume that $c_1(P^i) = 1$ and, w.l.o.g., that $c(v_1^{i+1}) = 1$. Therefore either $c_1(P^{i+1}) \ge 3$ or $c_1(P^{i+1}) = 2$ and $c(v_1^{i+2}) = 1$. Since the graph is finite the second case cannot happen indefinitely. Let $k > i$ be the smallest integer such that $c_1(P^k) \ge 3$. Then,

$$ \sum_{j=i}^{k} c_{1}(P^{j}) = c_{1}(P^{i}) + \sum_{j=i+1}^{k-1} c_{1}(P^{j}) + c_{1}(P^{k}) \\ \geq 1 + 2(k - i - 1) + 3 = 2(k - i + 1) $$

Consequently, for each path in $P^i, \dots, P^k$ we can “count” at least 2 vertices with color 1. Furthermore, this bound holds even if $k = \frac{n}{2}$ and $c(v_{12}^k) \neq 1$, for that reason, all these vertices have degree 2.

Now suppose that there is a path $P^{i'}$, with $i < k < i'$, such that $c_1(P^{i'}) = 1$, $c(v_{12}^{i-1}) = 1$ and $k$ is the greatest integer smaller than $i'$ such that $c_1(P^k) \ge 3$. By the same reasons of the last paragraph, we can conclude that for every $k < j < i'$, $c_1(P^j) = 2$ and $c(v_{12}^k) = 1$. Since $c(v_1^k) = 1$ and $c(v_{12}^k) = 1$ then $c_1(P^k) = 4$. For that reason,

$$ \sum_{j=i}^{i'} c_1(P^j) = c_1(P^i) + \sum_{j=i+1}^{k-1} c_1(P^j) + c_1(P^k) + \sum_{j=k+1}^{i'-1} c_1(P^j) + c_1(P^{i'}) \\ = 1 + 2(k - i - 1) + 4 + 2(i' - k - 1) + 1 = 2(i' - i + 1) $$

Therefore, for each path in $P^i, \dots, P^{i'}$ we can “count” exactly 2 vertices with color 1.

Finally, we can conclude that using the strategy above, by the end of the game $\sum_{i=1}^{\frac{n}{12}} c_1(P^i) \ge 2\frac{n}{12}$. □
The above proof can be easily adapted for $C_n$. Note also that the strategy described for Bob also works if Alice is allowed to skip her turn, i.e., Bob can ensure a monochromatic set of size at least $2^{n/12}$ even if Alice is allowed to skip some of her turns.

**Theorem 5.**

$$4 \lfloor \frac{n}{12} \rfloor + 1 \le \chi_{hg}(P_n) \le \frac{2(n+3)}{3},$$

and

$$4 \lfloor \frac{n}{12} \rfloor + 1 \le \chi_{hg}(C_n) \le \frac{2(n+3)}{3}.$$

*Proof.* The upper bounds directly follow from Corollary 2. The lower bound for paths follows Lemma 3 and the lower bound for cycles follows a direct adaptation of the proof of Lemma 3. □

# 5 Grids

A grid with $n$ rows and $m$ columns is a graph with vertex set $V = \{v_{i,j} | 1 \le i \le n \land 1 \le j \le m\}$. We say that the vertex $v_{i,j}$ is on row $i$ and column $j$. For the Cartesian, triangular and king grids, the set of edges are respectively:

$$\bullet E_{\square} = \{v_{i,j}v_{k,l} | (i = k \land j - l = \pm 1) \lor (j = l \land i - k = \pm 1)\}$$

$$\bullet E_{\triangle} = E_{\square} \cup \{v_{i,j}v_{k,l} | i - k = j - l = 1\}$$

$$\bullet E_{\bigcirc} = E_{\triangle} \cup \{v_{i,j}v_{k,l} | i - k = l - j = 1\}$$

<figure><img src="image_4.png" /><figcaption>Figure 3: Cartesian, triangular and king grids.</figcaption></figure>

The results on paths may be somehow extended to grids. On this section we use the some of the bounds already obtained to show bounds for the harmonious coloring game on Cartesian, triangular and king grids.

**Lemma 4.** Let $G$ be a grid graph with $n$ rows and $m$ columns, then:

$$\bullet \chi_{hg}(G) \ge 8 \lfloor \frac{n-2}{5} \rfloor \lfloor \frac{m}{12} \rfloor + 1, \text{ if } G \text{ is a Cartesian grid;}$$

$$\bullet \chi_{hg}(G) \ge 12 \lfloor \frac{n-4}{5} \rfloor \lfloor \frac{m}{12} \rfloor + 1, \text{ if } G \text{ is a triangular grid;}$$

$$\bullet \chi_{hg}(G) \ge 16 \lfloor \frac{n-6}{5} \rfloor \lfloor \frac{m}{12} \rfloor + 1, \text{ if } G \text{ is a king grid.}$$

*Proof.* For each type of grid, let $i$ and $j_i$ be the integers defined below:

$$\bullet 1 \le i \le \lfloor \frac{n-2}{5} \rfloor \text{ and } j_i = 5i - 3 \text{ for the Cartesian grid;}$$

$$\bullet 1 \le i \le \lfloor \frac{n-4}{5} \rfloor \text{ and } j_i = 5i - 2 \text{ for the triangular grid;}$$

$$\bullet 1 \le i \le \lfloor \frac{n-6}{5} \rfloor \text{ and } j_i = 5i - 1 \text{ for the king grid;}$$
Let $P^i$ be the path induced by the vertices on row $j_i$ of the grid and let $v_k^i$ be the vertex of $P^i$ on the $k$-th column of the grid.

To achieve the bounds described above, Bob plays using his strategy for the paths, described on Lemma 3, on the vertices of each $P^i$. That is, for each of these paths, Bob wants to have at least $2\lfloor\frac{m}{12}\rfloor$ internal vertices with color 1.

Notice that, in the proof of Lemma 3, Bob's strategy is only concerned in the vertices for which the color 1 is forbidden. Furthermore is worth noticing that Bob's strategy works even when Alice can skip her turn, since this cannot decrease the number of vertices colored with 1 by the end of the game. In the case Alice does so, Bob can just choose an internal vertex of any of the subpaths and color it, preferably with color 1, such that the number of vertices that can still receive color 1 in the subpath are maximized after Bob's move.

Observe that if Alice colors a vertex $v$ at distance at most 2 from a vertex of some $P^i$, Bob's strategy is not affected on any $P^k$ when $k \neq i$. Therefore, when Alice colors a vertex $v$ with color $c$ at distance at most 2 from the path $P^i$, Bob can use a strategy analogous to the one on Lemma 3 as if Alice had played on a vertex of $P^i$. Obviously if Alice colors a vertex of $P^i$, Bob just follows his strategy as in Lemma 3.

More precisely, there are three cases depending on the type of the considered grid.

**Cartesian Grid.** There are 2 possibilities when Alice colors a vertex at distance 1 or 2 from $P^i$ on the Cartesian grid:

* If Alice colors a vertex on column $k$ on rows $j_i \pm 1$ with any color $c$ or on rows $j_i \pm 2$ with color 1, she forbids, on the worst case, the vertices $v_k^i$, $v_{k+1}^i$ and $v_{k-1}^i$ from receiving color 1. Therefore, for Bob's strategy on $P^i$, this is equivalent to Alice coloring $v_k^i$ with a color $c' \neq 1$.

* If Alice colors a vertex on rows $j_i \pm 2$ with color $c \neq 1$, she does not forbid the use of color 1 for any new vertices on $P^i$. Bob plays in $P^i$ as if Alice had passed her turn.

Clearly this strategy leads to at least $2\lfloor\frac{m}{12}\rfloor$ vertices with color 1 for each $P^i$ on the Cartesian grid.

**Triangular Grid.** For the triangular grid, there are 3 possibilities when Alice colors a vertex at distance 1 or 2 from $P^i$:

* If Alice colors a vertex on column $k$ on rows $j_i \pm 1$ with color $c \neq 1$ or on rows $j_i \pm 2$ with $c = 1$, she forbids, in the worst case, the color 1 from being used on the vertices $v_{k-2}^i$, $v_{k-1}^i$ and $v_k^i$. Therefore, for Bob's strategy on $P^i$, this is equivalent to Alice coloring the vertex $v_{k-1}^i$ with a color $c' \neq 1$.

* If Alice colors a vertex on column $k$ on rows $j_i \pm 1$ with color $c = 1$, she forbids color 1 for the vertices $v_{k-2}^i$, $v_{k-1}^i$, $v_k^i$ and $v_{k+1}^i$. Then Bob can just assume that Alice colored $v_k^i$ with color 1 and follow his strategy on $P^i$. Note that, in this case, the vertex colored by Alice and $v_k^i$ have the same degree.

* If Alice colors a vertex on rows $j_i \pm 2$ with color $c \neq 1$, she does not forbid the use of color 1 for any new vertices on $P^i$. Bob plays in $P^i$ as if Alice had passed her turn.

Clearly this strategy leads to at least $2\lfloor\frac{m}{12}\rfloor$ vertices with color 1 for each $P^i$ on the triangular grid.

**King Grid.** There are 3 possibilities when Alice colors a vertex at distance 1 or 2 from $P^i$ on the king grid:

* If Alice colors a vertex on column $k$ on rows $j_i \pm 1$ or $j_i \pm 2$ with color $c = 1$, she forbids color 1 for the vertices $v_{k-2}^i$, $v_{k-1}^i$, $v_k^i$, $v_{k+1}^i$ and $v_{k+2}^i$. Then Bob can just assume that Alice colored $v_k^i$ with color 1 and follow his strategy on $P^i$. Note that, in this case, the vertex colored by Alice and $v_k^i$ have the same degree.

* If Alice colors a vertex on column $k$ on rows $j_i \pm 1$ with color $c \neq 1$, she forbids, on the worst case, the vertices $v_k^i$, $v_{k+1}^i$ and $v_{k-1}^i$ from receiving color 1. Therefore, for Bob's strategy on $P^i$, this is equivalent to Alice coloring $v_k^i$ with a color $c' \neq 1$.
* If Alice colors a vertex on rows $j_i \pm 2$ with color $c \neq 1$, she does not forbid the use of color 1 for any new vertices on $P^i$. Bob plays in $P^i$ as if Alice had passed her turn.

Clearly this strategy leads to at least $2 \lfloor \frac{m}{12} \rfloor$ vertices with color 1 for each $P^i$ on the king grid.

Since each of the vertices colored with 1 for each $P^i$ have degrees 4, 6 and 8 for the Cartesian, triangular and king grids respectively, we obtain the desired bounds by Lemma 1. □

**Theorem 6.** Let $G$ be a grid graph with $n > 3$ rows and $m > 1$ columns, then:

* $8 \lfloor \frac{n-2}{5} \rfloor \lfloor \frac{m}{12} \rfloor + 1 \le \chi_{hg}(G) \le \frac{4nm}{5} + 4$, if $G$ is a Cartesian grid;

* $12 \lfloor \frac{n-4}{5} \rfloor \lfloor \frac{m}{12} \rfloor + 1 \le \chi_{hg}(G) \le \frac{6nm}{7} + 6$, if $G$ is a triangular grid;

* $16 \lfloor \frac{n-6}{5} \rfloor \lfloor \frac{m}{12} \rfloor + 1 \le \chi_{hg}(G) \le \frac{8nm}{9} + 8$, if $G$ is a king grid;

*Proof.* The upper bounds directly follow Corollary 2. The lower bounds come from Lemma 4. □

# 6 Forests of Stars

We are interested in this graph class because it is known that computing the harmonious chromatic number of a forest of stars is NP-complete [10]. For any graph $G = (V, E)$ and $v \in V$, let $deg(v)$ denote the degree of the vertex $v$.

**Claim 6.** Let $S$ and $S'$ be two stars with $n$ and $m$ leaves respectively, $n \ge m$. Then, $\chi_{hg}(S) = n + 1$ and $\chi_{hg}(S \cup S') = n + 1$ if $n > m$ and $\chi_{hg}(S \cup S') = n + 2$ otherwise.

*Proof of Claim.* Since any harmonious coloring must be proper at distance 2, and $\chi_{hg}(G) \le |V(G)|$ for any graph $G$, we get $\chi_{hg}(S) = n + 1$.

In the disjoint union $S \cup S'$, Alice starts by coloring a leaf of $S$ with color 1. If, at his first turn, Bob has not colored the center of $S'$, Alice colors it with the smallest possible color. If Bob has colored the center of $S'$ with a color distinct from 1, then Alice colors a leaf of $S'$ with 1. From now, Alice plays greedily. This strategy is winning with $n + 1$ (or $n + 2$ if $n = m$) colors which is optimal since it equals the harmonious number of $S \cup S'$. ◇

**Lemma 5.** Let $G = S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n$ where each $S_i$ is a star with center $s_i$ such that $deg(s_1) \ge deg(s_2) \ge deg(s_3) \ge \dots \ge deg(s_n)$. Then:

$$ \chi_{hg}(G) \ge 1 + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} deg(s_{2i-1}) $$

*Proof.* Let 1 be the color used by Alice at her first turn. If Alice colored the center of a star at her first turn, let $c = 1$ and let $c = 2$ otherwise. While it is possible, the strategy of Bob consists of coloring the vertex $s_j$ with color $c$, where $j$ is the smallest integer such that $s_j$ is uncolored.

**Claim 7.** After the $j$-th move of Bob ($0 < j \le \lfloor \frac{n}{2} \rfloor$), $s_1$ is colored with color $c$ and, for every $0 < i \le j$, at least $i - 1$ vertices are colored with $c$ in $\{s_2, s_3, \dots, s_{2j-1}\}$.

*Proof of Claim.* The proof is by induction on $j$. If $j = 1$, if Alice's first move colors a center $s$ (with color 1), then $c = 1$ and either $s = s_1$ or $s \neq s_1$ and Bob's first move consists in coloring $s_1$ with $c$. If Alice does not color a center, then Bob colors $s_1$ with $c$. In all cases, we are done.

Let us assume by induction that the result holds for the $j$th turn. If, at the $(j+1)$-th turn of Bob, $s_{2j}$ or $s_{2j+1}$ can be colored with $c$, then Bob colors a vertex $s_k$, $k \le 2j + 1$, with color $c$. Then, the result holds. Otherwise (if none of $s_{2j}$ or $s_{2j+1}$ can be colored with $c$), it implies that Alice has already colored one vertex in each of $S_{2j}$ and $S_{2j+1}$. Therefore, some star in $\{S_2, \dots, S_{2j-1}\}$ has no vertex colored yet. Then, Bob colors a vertex $s_k$, $k \le 2j - 1$, with color $c$. This concludes the proof of the claim. ◇

It follows that the centers colored with color $c$ are (all together) adjacent to at least $\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} deg(s_{2i-1})$ vertices. Therefore, $\chi_{hg}(G) \ge 1 + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} deg(s_{2i-1})$. □
**Lemma 6.** Let $G = S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n$ where each $S_i$ is a star with center $s_i$ such that $\deg(s_1) \ge \deg(s_2) \ge \deg(s_3) \ge \dots \ge \deg(s_n)$. Then:

$$ \chi_{hg}(G) \le 2 + \lfloor \frac{n}{2} \rfloor + \deg(s_1) + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} \deg(s_{2i}) $$

*Proof.* Note that we may assume that $\deg(s_j) > 0$ for any $j \le n$ since isolated vertices do not create any constraint. Hence, $\deg(s_j) \ge 1$ for every $1 \le j \le n$.

Let $y = 2 + \lfloor \frac{n}{2} \rfloor + \deg(s_1) + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} \deg(s_{2i})$ and let us show that Alice has a winning strategy using $y$ colors. Note that $y \ge n$.

Alice first colors $s_1$ with color 1. While there is an uncolored center, at her turn:

* if Bob has just colored a center $s_i$ with $\{i, i'\} = \{2k, 2k+1\}$ and $s_{i'}$ is uncolored, then Alice colors $s_{i'}$ with a new color (a color she has not used yet).

* otherwise, Alice colors the uncolored center with smallest index with a new (a color she has not used yet) color (note that this color could have been used by Bob).

Once all centers have been colored, Alice greedily colors any uncolored vertex with the smallest possible color.

First, let us show that, while all centers are not colored, then the Alice's strategy is valid, i.e., there is a color available for Alice. Consider such a turn $j$ (so $1 < j \le n$) when Alice has to color some center $s_i$. Up to this turn, at most $j-1$ leaves may have been colored (by Bob, since Alice only colored centers until now) and so at most $j-1 < n \le y$ forbidden pairs of colors are forbidden. Therefore, there must be a color available for Alice.

Note that the same argument holds for Bob, and so, while not all centers have been colored, Bob can always play.

For purpose of contradiction, let us assume that the Alice's strategy is not winning. So, at some turn $j$, Alice (or Bob) cannot color any vertex with any of the $y$ colors. By above paragraph, all centers must have been colored (and so $j > n$). Let $f$ be any uncolored leaf and let $s_i$ be the center of the star containing $f$ and let $c$ be the color of $s_i$. Let $X = X_c \cup X_f$ be the set of vertices colored with $c$ before turn $j$ where $X_c$ is the set of centers colored with $c$ and $X_f$ is the set of leaves colored with $c$ (at most one vertex per star with the center not colored $c$). The number of forbidden pairs of colors containing $c$ is then at most $1 + |X_f| + \sum_{s_k \in X_c} \deg(s_k) - 1$. Note that $|X_c| + |X_f| \le n$.

Note that Alice's strategy ensures that, for every color $c$ and every integer $i \in [1, \lfloor \frac{n}{2} \rfloor]$ but at most one such integer, $c(s_{2i}) \ne c$ or $c(s_{2i+1}) \ne c$. Note also that for $c = 1$ all $i \in [1, \lfloor \frac{n}{2} \rfloor]$ satisfies such condition.

Therefore, by previous sentence,

$$ |X_f| + \sum_{s_k \in X_c} \deg(s_k) - 1 \le |X_f| + \deg(s_1) + \sum_{i=1}^{|X_c|} \deg(s_{2i}) - 1 $$

Hence, since $|X_c| + |X_f| \le n$,

$$ |X_f| + \sum_{s_k \in X_c} \deg(s_k) - 1 \le n - |X_c| + \deg(s_1) + \sum_{i=1}^{|X_c|} \deg(s_{2i}) - 1 $$

Therefore, because $\deg(s) > 0$ for every center $s$,

$$ |X_f| + \sum_{s_k \in X_c} \deg(s_k) - 1 \le \lfloor \frac{n}{2} \rfloor - 1 + \deg(s_1) + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} \deg(s_{2i}), $$
and so

$$|X_f| + \sum_{s_k \in X_c} \deg(s_k) - 1 \leq \lfloor \frac{n}{2} \rfloor + \deg(s_1) + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} \deg(s_{2i})$$

and so

$$1 + |X_f| + \sum_{s_k \in X_c} \deg(s_k) - 1 < y$$

which contradicts the fact that Alice (or Bob) cannot color a vertex at her turn. □

**Theorem 7.** Let $n \geq 3$. For any forest $G$ of $n$ stars with centers with degree $d_1 \geq d_2 \geq \dots \geq d_n$:

$$1 + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} d_{2i-1} \leq \chi_{hg}(G) \leq 2 + \lfloor \frac{n}{2} \rfloor + d_1 + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} d_{2i}$$

# 7 Conclusions and Open Problems

In this paper, we have introduced the Harmonious Coloring Game (HCG), a new two player game related to the harmonious coloring problem. We proved that three variants of this game are PSPACE-complete: Sequential HCG, Pre-Colored HCG and Bob-Restricted HCG. As a by-product, we also proved that the Chromatic Game II, a game introduced in 1997 by Chen et al. [5], is also PSPACE-complete.

Despite that, we were unable to prove the computational complexity of the original HCG. One of the difficulties is that, for a given graph $G = (V, E)$ and the constructed graph $\tilde{G}$ in the proof of Theorems 1 and 4, it is not true that $\chi_g(G) = k$ if and only if $\chi_{hg}(\tilde{G}) = k + |E|$, since Bob can, at each of his turns on $\tilde{G}$, use a new color on a vertex of $V$. If $k$ is small enough compared to $|E|$, Bob can use $k+1$ distinct colors on the vertices of $V$ at some point of the game and the clique cannot be fully colored anymore. Nevertheless, the following seems reasonable.

**Conjecture 1.** The harmonious coloring game is PSPACE-complete. That is, given a graph $G$ and an integer $k$, deciding if $\chi_{hg}(G) \leq k$ is PSPACE-complete.

We also obtained lower and upper bounds for general graphs and for some graph classes. However, we were unfortunately unable to determine the exact value of the harmonious game chromatic number even for paths and cycles.

**Question 1.** What is the exact value of $\chi_{hg}(P_n)$ and $\chi_{hg}(C_n)$ for every $n \geq 1$?

# References

[1] K. Asdre, K. Ioannidou, and S. Nikolopoulos. The harmonious coloring problem is np-complete for interval and permutation graphs. Discret. Appl. Math., 155(17):2377-2382, 2007.

[2] H. L. Bodlaender. On the complexity of some coloring games. Int. J. Found. Comput. Sci., 2(2):133-147, 1991.

[3] Martin Böhm and Pavel Veselý. Online chromatic number is pspace-complete. Theory Comput. Syst., 62(6):1366-1391, 2018.

[4] T. Bohman, A. Frieze, and B. Sudakov. The game chromatic number of random graphs. Random Struct. Algor., 32(2):223-235, 2008.

[5] G. Chen, R. H. Schelp, and W. E. Shreve. A new game chromatic number. Eur. J. Comb., 18(1):1-9, 1997.

[6] E. R. Costa, V. L. Pessoa, R. Sampaio, and R. Soares. PSPACE-completeness of two graph coloring games. Theor. Comput. Sci., 824-825:36-45, 2020.
[7] T. Dinski and X. Zhu. A bound for the game chromatic number of graphs. *Discrete Math.*, 196(1):109-115, 1999.

[8] K. Edwards. The harmonious chromatic number of complete r-ary trees. *Discret. Math.*, 203(1-3):83-99, 1999.

[9] K. Edwards and C. McDiarmid. New upper bounds on harmonious colorings. *J. Graph Theory*, 18(3):257-267, 1994.

[10] K. Edwards and C. McDiarmid. The complexity of harmonious colouring for trees. *Discret. Appl. Math.*, 57(2-3):133-144, 1995.

[11] U. Faigle, U. Kern, H. Kierstead, and W. Trotter. On the game chromatic number of some classes of graphs. *Ars Combinatoria*, 35:143-150, 1993.

[12] G. Fickes and W. H. Wong. The edge-distinguishing chromatic number of petal graphs, chorded cycles, and spider graphs. *Electron. J. Graph Theory Appl.*, 10(2):393, September 2022.

[13] O. Frank, F. Harary, and M. Plantholt. The line-distinguishing chromatic number of a graph. *Ars Combinatorics*, 14:241-252, 1982.

[14] M. Gardner. Mathematical games. *Scientific American*, 244(4):18-26, 1981.

[15] J. P. Georges. On the harmonious coloring of collections of graphs. *J. Graph Theory*, 20(2):241-254, 1995.

[16] H. A. Kierstead and W. T. Trotter. Planar graph coloring with an uncooperative partner. *J. Graph Theory*, 18(6):569-584, 1994.

[17] Christian Kudahl. Deciding the on-line chromatic number of a graph with pre-coloring is pspace-complete. In Vangelis Th. Paschos and Peter Widmayer, editors, *Algorithms and Complexity - 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings*, volume 9079 of Lecture Notes in Computer Science, pages 313-324. Springer, 2015.

[18] C. V. Lima, T. Marcilon, N. Martins, and R. Sampaio. PSPACE-hardness of variants of the graph coloring game. *Theor. Comput. Sci.*, 909:87-96, 2022.

[19] C.V. Lima, T. Marcilon, N. Martins, and R. Sampaio. The connected greedy coloring game. *Theor. Comput. Sci.*, 940:1-13, 2023.

[20] J. Mitchem. On the harmonious chromatic number of a graph. *Discret. Math.*, 74(1-2):151-157, 1989.