In 2003, the frequency assignment problem in a cellular network motivated Even et al. to introduce a new coloring problem: Conflict-Free coloring. Inspired by this problem and by the Gardner-Bodlaender’s coloring game, in 2020, Chimelli and Dantas introduced the Conflict-Free Closed Neighborhood \(k\)-coloring game (CFCN \(k\)-coloring game). The game starts with an uncolored graph \(G\), \(k\geq 2\) different colors, and two players, Alice and Bob, who alternately color the vertices of \(G\). Both players can start the game and respect the following legal coloring rule: for every vertex \(v\), if the closed neighborhood \(N[v]\) of \(v\) is fully colored then there exists a color that was used only once in \(N[v]\). Alice wins if she ends up with a Conflict-Free Closed Neighborhood \(k\)-coloring of \(G\), otherwise, Bob wins if he prevents it from happening. In this paper, we introduce the game for open neighborhoods, the Conflict-Free Open Neighborhood \(k\)-coloring game (CFON \(k\)-coloring game), and study both games on graph classes determining the least number of colors needed for Alice to win the game.
We consider undirected, finite and simple graphs \(G=(V(G)\), \(E(G))\), where \(V(G)\) is the vertex set and \(E(G)\) is the edge set of \(G\). We say that vertices \(u,v \in V(G)\) are adjacent if \(uv\) is an edge of \(G\). The open neighborhood \(N(v)\) of a vertex \(v\) is the set of vertices that are adjacent to \(v\), and the closed neighborhood \(N[v]\) of vertex \(v\) is the union \(N(v)\cup \{v\}\). A vertex \(k\)-coloring of a graph \(G\) is a function \(c:V(G) \rightarrow \lbrace c_1,c_2,…,c_k\rbrace\), where \(\lbrace c_1,c_2,…,c_k\rbrace\) represents a set of \(k\) different colors.
In \(2003\), Even et al. [10] introduced the Conflict-Free coloring inspired by the Cellular Network problem: \(n\) base stations establish a link via radio frequencies, interference occurs if one particular mobile device establishes a link with two or more base stations that have the same radio frequency. So, every base station must contact a mobile device with a unique radio frequency. A solution for this problem can be obtained by assigning \(n\) different frequencies to the \(n\) base stations but, since having a lot of different frequencies is expensive, it is important trying to minimize their quantity, in a way that there is no interference.
The Conflict-Free coloring in graphs is obtained by modeling base stations as vertices, interference constraints as edges, and radio frequencies as colors, ensuring that every mobile device (neighborhood) has at least one uniquely colored base station. Therefore, the Conflict-Free coloring of a graph \(G\) consists of assigning different colors to the vertices of \(G\) such that, for every vertex \(v\), there exists a vertex \(v'\) in the neighborhood of \(v\), such that the color of \(v'\) differs from the color of every other vertex in the neighborhood of \(v\).
Formally, given a graph \(G\), a vertex \(k\)-coloring is called a Conflict-Free Closed Neighborhood \(k\)-coloring (CFCN \(k\)-coloring) if for every vertex \(v\in V(G)\), there exists a vertex \(v'\) in the closed neighborhood \(N[v]\) such that \(c(v')\not =c(w)\) for all \(w\in N[v]\setminus\{v'\}\). The complexity of these colorings in graphs were studied in [1], and in [13], where the authors prove that the CFCN coloring problem is NP-complete. Moreover, in \(2009\), Cheilaris considered these colorings not only on graphs, but also on hypergraphs [5], a scenario also studied by Smorodinsky [18] and Cui & Hu [7].
Let \(G\) be a graph and \(S\subseteq V(G)\), we say that \(S\) is fully colored if each vertex of \(S\) has a color assigned to it. A graph \(G\) together with a CFCN \(k\)-coloring is said to be CFCN \(k\)-colored. In Figure 1, we show an example of a graph \(G\) with a CFCN \(2\)-coloring.
Another approach to examining this problem is to consider it from the perspective of combinatorial games [2]. Combinatorial games have been studied from different perspectives (see for example impartial games [8], coloring [11,14,16,17,19], domination [4], and labeling [15]).
In \(1981\), Martin Gardner [12] introduced a combinatorial game, called coloring game, which was studied later by Bodlaender [3]. The game consists of two players, Alice and Bob, who alternately color uncolored vertices of a graph using \(k\) colors, such that adjacent vertices have different colors (proper coloring). Alice wins if she obtains a proper \(k\)-coloring of the graph; otherwise, Bob wins. Inspired by the coloring game, in 2020, Chimelli and Dantas [6] proposed the combinatorial game called CFCN \(k\)-coloring game for complete graphs of small order.
The CFCN \(k\)-coloring game is a combinatorial game in which two players, Alice and Bob, alternately color the vertices of a graph as follows. In each turn, a player assigns one of the \(k\) colors to one arbitrary vertex \(v\), in such a way that, after it, in every fully colored closed neighborhood to which \(v\) belongs, there exists a color that appears exactly once (legal coloring). Thus, for every \(u \in V\), if \(N[u]\) is fully colored, then there exists \(u' \in N[u]\) such that \(c(u')\neq c(w)\) for all \(w \in N[u]\setminus\{u'\}\). Either Alice or Bob starts the game, they cannot skip turns, they play optimally, and they are constrained to use only legal colorings (moves) in each turn. Alice wins if it is guaranteed that she can obtain a CFCN \(k\)-coloring of \(G\), otherwise Bob wins if he prevents it from happening.
We remark that, by play optimally, we mean that the players try to win with the fewest possible turns or, in case of knowing that it is not possible to win the game, delay the opponent’s victory. For example, suppose Alice and Bob play the CFCN \(2\)-coloring game on a star \(S_{n-1}\) graph (complete bipartite \(K_{1,n-1}\), with \(n\geq 3\)). If Alice starts the game, then the best option for her is to color the central vertex (vertex of degree \(n-1\)) with a color \(c_1\). She immediately wins the game because, by the legal coloring rule, in each turn, the vertices of degree one must be colored with a different color \(c_2\). Else, if Bob starts the game (see Figure 2) then, to delay Alice’s victory, he colors any vertex other than the central one. So, in the second turn, Alice colors the central vertex and wins.
In the present work, we introduce the Conflict-Free Open Neighborhood \(k\)-coloring game (CFON \(k\)-coloring game), and contribute to this subject by studying the behavior of both games on some classic graph classes such as stars, complete graphs, paths, cycles.
In order to extend the results on complete graphs, we also analyze the behavior of this coloring on cliques in graphs studying windmill graphs and their generalization. Windmill graphs have been much studied since Erdös, Rényi and Sós [9] (1966) established that the only graphs with the property that every two vertices have exactly one neighbor in common are the friendship graphs, which are members of this larger family called windmill graphs.
The windmill graph \(W(n,p)\), \(n\geq 2\), \(p\geq2\), is a graph constructed by joining \(p\) copies of the complete graph \(K_n\) to a unique universal vertex \(u\). We refer to Figure 3 for an example of the CFCN \(2\)-coloring game played on a windmill graph \(G=W(3,3)\), where Alice’s turns are \(A_1\) and \(A_3\), and Bob’s turns are \(B_2\) and \(B_4\). Alice starts the game, and Bob wins on the fourth turn since all colors are duplicated in the closed neighborhood of vertex \(u\).
This paper is organized as follows. In Section 2, we introduce the game and show definitions and notation. From Sections 3 to 7, we study the CFCN \(k\)-coloring game and the CFON \(k\)-coloring game on stars, complete graphs, paths, cycles, and windmill graphs and their generalizations. In each of the studied graph classes, we show strategies that determine the least number of colors necessary so that Alice wins the game. Finally, in Section 8, we present our final remarks.
Let \(V'\) be a nonempty subset of \(V\). The subgraph \(H=(V',E')\) of \(G\) whose vertex set is \(V'\), and whose edge set \(E'\) is the set of edges of \(G\) that have both incident vertices in \(V'\) is called the subgraph of \(G\) induced by \(V'\), and it is denoted by \(G[V']\); we say that \(G[V']\) is an induced subgraph of \(G\).
We recall that a vertex \(k\)-coloring of a graph \(G\) is called a Conflict-Free Closed Neighborhood \(k\)-coloring (CFCN \(k\)-coloring) if for every vertex \(v\in V(G)\), there exists a vertex \(u\) in the closed neighborhood \(N[v]\) such that \(c(u)\not =c(w)\) for all \(w\in N[v]\setminus\{u\}\). Similarly a vertex \(k\)-coloring is called a Conflict-Free Open Neighborhood \(k\)-coloring (CFON \(k\)-coloring) if for every vertex \(v\in V(G)\), there exists a vertex \(u\) in the open neighborhood \(N(v)\) such that \(c(u)\not =c(w)\) for all \(w\in N(v)\setminus\{u\}\).
We say that \(N[v]\) (resp. \(N(v)\)) is fully colored if each vertex of \(N[v]\) (resp. \(N(v)\)) has a color assigned to it. A graph \(G\) together with a CFCN \(k\)-coloring (resp. CFON \(k\)-coloring) is said to be CFCN \(k\)-colored (resp. CFON \(k\)-colored). A coloring of a vertex \(v\) is said to be a legal coloring of \(v\) if, after it, in every fully colored neighborhood in which \(v\) belongs, there exists a color that appears exactly once.
Formally, the Closed (resp. Open) Neighborhood Conflict-Free Chromatic Number of \(G\), denoted by \(\chi_{CN}(G)\) (resp. \(\chi_{ON}(G)\)), is the minimum number \(k\) of colors necessary for \(G\) to be CFCN \(k\)-colored (resp. CFON \(k\)-colored). Now, we are ready to present the rules of the game.
The CFCN \(k\)-coloring game (resp. CFON \(k\)-coloring game) is a combinatorial game in which two players, Alice and Bob, take turns (alternately) coloring the vertices of a graph as follows. In each turn, a player assigns one of the \(k\) colors to one arbitrary vertex \(v\), in such a way that, after it, in every fully colored closed neighborhood in which \(v\) belongs, there exists a color that appears exactly once (legal coloring). Thus, for every \(u \in V\), if \(N[u]\) is fully colored, then there exists \(u' \in N[u]\) such that \(c(u')\neq c(w)\) for all \(w \in N[u]\setminus\{u'\}\). Either Alice or Bob starts the game, they cannot skip turns, they play optimally (as explained in the Introduction section), and they are constrained to use only legal colorings (moves) in each turn. Alice wins if it is guaranteed that she can obtain a CFCN \(k\)-coloring (resp. CFON \(k\)-coloring) of \(G\), otherwise Bob wins if he prevents it from happening.
We denote by \(\chi^g_{CN}(G)\) (resp. \(\chi^g_{ON}(G)\)), the Closed (resp. Open) Neighborhood Conflict-Free game Chromatic Number of \(G\), that is, the minimum number \(k\) of colors necessary for Alice to have a winning strategy for the CFCN (resp. CFON) \(k\)-coloring game on \(G\), independent of who starts the game.
Next, we analyze the game on stars, complete graphs, paths, cycles, and windmill graphs and their generalization.
A star graph \(S_{n-1}\) is a tree on \(n\) vertices such that one vertex \(v_0\) has degree \(n-1\) (central vertex) and the other \(n-1\) vertices have degree \(1\).
We consider CFCN \(k\)-coloring game and prove that \(\chi^g_{CN}(S_{n-1})=2\); and we also study the CFON \(k\)-coloring game and prove that \(\chi^g_{ON}(S_{n-1})=\lceil{\frac{n-1}{4}} \rceil+1\).
Theorem 3.1. Alice wins the CFCN \(k\)-coloring game on a Star \(S_{n-1}\) with \(n>2\) vertices and \(k\geq 2\) colors, independently of who starts playing.
Proof. If Alice starts the game, then she colors the central vertex \(v_0\) with a color \(c(v_0)\) and wins. Indeed, since \(N[v]=\{v_0, v\}\) for each \(v\in V(S_{n-1})\setminus v_0\), by the legal coloring rule, no other vertex can be colored with \(c(v_0)\).
Similarly, if Bob starts the game then, since he plays optimally, he does not color the central vertex in order to delay Alice’s victory. However, in the second turn, Alice colors the central vertex and wins. ◻
Theorem 3.2. Alice wins the CFON \(k\)-coloring game played on a star \(S_{n-1}\) with \(n>2\) vertices, when she starts the game, if and only if, \(k > \lceil{\frac{n-2}{4}} \rceil\).
Proof. Since \(N(v_0)=V(S_{n-1})\setminus\{v_0\}\) and \(N(v)=v_0\) for every \(v\neq v_0\), to obtain a CFON \(k\)-coloring for \(S_{n-1}\), at least one color must appear exactly once in \(N(v_0)\). We also remark that the colors chosen for \(N(v_0)\) (resp. \(v_0\)) do not affect the decision for the color of the vertex \(v_0\) (resp. vertices in \(N(v_0)\)).
In that case, to prevent a color from appearing only once in \(N(v_0)\), Bob’s strategy is to duplicate all \(k\) colors in \(N(v_0)\). To delay this duplication, Alice chooses as few colors as possible using colors that have already been duplicated.
In addition, Alice starts the game by coloring the central vertex to ensure that duplication of the first two colors in \(N(v_0)\) takes five turns instead of four (see Figure 4).
With the aforementioned strategies, it is immediate to demonstrate that, from the second turn, every \(4t+1\) turns Alice and Bob have used exactly \(t+1\) colors and each of them has been used at least twice.
If \(|N(v_0)|\leq 5\), then it is clear that two colors are necessary for Alice to win (See Figure 5). If \(|N(v_0)|>5\), then there exists \(t\in\mathbb{N}\) such that \(4t+1<|N(v_0)|\leq 4(t+1)+1\), and since \(|N(v_0)|=n-1\), we have that \(4t+1<n-1\leq 4(t+1)+1\).
Suppose that \(k \leq \lceil{\frac{n-2}{4}} \rceil\). Thus, we have that \[k\leq\left \lceil{{\frac{n-2}{4}}}\right \rceil \leq \left \lceil{{\frac{4(t+1)}{4}}}\right \rceil=t+1.\]
Hence, by the time Alice and Bob have colored \(4t+1\) vertices, they have already used all the \(k\) colors at least twice. Furthermore, since \(4t+1<|N(v_0)|\), the graph is not fully colored and Bob wins the game because there exists no available color to use only once.
Reciprocally, if \(k > \lceil{\frac{n-2}{4}} \rceil\), since \(4t<n-2\leq 4(t+1)\), then \(t<\lceil{\frac{n-2}{4}} \rceil\leq t+1\). Thus, \(t+1=\lceil{\frac{n-2}{4} \rceil}<k\). So, \(k\geq t+2\) and, by the legal coloring rule, to duplicate \(t+2\) colors, Bob needs at least \(4(t+1)+2\) vertices in \(N(v_0)\). Since \(|N(v_0)|\leq 4(t+1)+1\), Alice wins the game. ◻
Theorem 3.3. Alice wins the CFON \(k\)-coloring game played on a star \(S_{n-1}\) on \(n>2\) vertices, when Bob starts the game, if and only if, \(k > \lceil{\frac{n-1}{4}} \rceil\).
Proof. The proof is similar to that of Theorem 3.2 since to prevent a color from appearing only once, Bob’s strategy is to duplicate all \(k\) colors in \(N(v_0)\) and, to delay this duplication, Alice chooses as few colors as possible using colors that have already been duplicated. If Bob starts the game and colors the central vertex, then he duplicates the first two colors in the next four turns and reduces the number of turns by one to win the game (see Figure 6). If Bob starts the game and colors a vertex in \(N(v_0)\), then it is the same as what we have in Theorem 3.2. ◻
A complete graph \(K_n\) with \(n\) vertices is a graph in which every pair of distinct vertices is joined by an edge. In the next results we prove that \(\chi^g_{CN}(K_n)=\lceil{\frac{n}{4}} \rceil+1\), for \(n\geq 2\), and \(\chi^g_{ON}(K_n)=\lceil{\frac{n+7}{4}} \rceil\), for \(n\geq 7\).
In the context of CFCN coloring of complete graphs, a question arises regarding why Bob cannot simply replicate the color used by Alice in her preceding move. For example, if Alice begins and the graph contains an even number of vertices, this strategy results in an invalid coloring by the legal coloring rule. Moreover, with the strategy presented in the next result, Bob duplicates more colors in fewer turns.
Theorem 4.1. Alice wins the CFCN \(k\)-coloring game on a complete graph \(K_n\), \(n\geq 2\), when she starts, if and only if \(k>\left \lceil{{\frac{n}{4}}}\right \rceil\).
Proof. Since \(N[v]=V(K_n)\), for every vertex \(v\in V(K_n)\), to obtain a CFCN \(k\)-coloring for \(K_n\), we observe that: \((i)\) at least one color must appear only once in \(V(K_n)\); and \((ii)\) until coloring the last vertex in \(K_n\) no neighborhood is fully colored.
To prevent one color from appearing exactly once, Bob’s strategy is to duplicate all \(k\) colors in \(V(K_n)\), and to delay this duplication, Alice chooses as few colors as possible using colors that have already been duplicated. Thus, since Alice starts the game with a color \(c_1\) (and chooses this color in her next turn), in the second turn, Bob colors a vertex with a color \(c_2 \neq c_1\), to maximize the number of duplicated colors in the first four turns. Hence, he obtains two duplicated colors in the first four turns, as shown in Figure 7.
So, for every \(4t\) turns Alice and Bob have used exactly \(t+1\) colors and each of them has been used at least twice.
Suppose that \(k \leq\) \(\left \lceil{{\frac{n}{4}}}\right \rceil\) and \(n>4\). Thus, there exists \(t\in\mathbb{N}\) such that \(4t<n\leq 4(t+1)\). Therefore, \[k\leq\left \lceil{{\frac{n}{4}}}\right \rceil\leq\left \lceil{{\frac{4(t+1)}{4}}}\right \rceil=t+1,\] and since \(|V(K_n)|>4t\), we have that, by the time Alice and Bob have colored \(4t\) vertices, they have already used all the \(k\) colors at least twice, and the graph is not fully colored. Hence, Bob wins the game because there exists no color available to use only once.
Reciprocally, if \(k > \lceil{\frac{n}{4}} \rceil\), since \(4t<n\leq 4(t+1)\), we have that \(t<\lceil{\frac{n}{4}} \rceil\leq t+1\), and so \(\lceil{\frac{n}{4}}\rceil=t+1\). Thus, \(k> \lceil{\frac{n}{4}} \rceil \geq t+2\) and Bob needs at least \(4(t+1)+1\) vertices to duplicate \(t+2\) colors. Hence, Alice wins since \(|N(v)|\leq 4(t+1)\). ◻
Theorem 4.2. Alice wins the CFCN \(k\)-coloring game on a complete graph \(K_n\), \(n\geq 2\), when Bob starts, if and only if \(k\) \(>\) \(\left \lceil{{\frac{n-1}{4}}}\right \rceil\).
Proof. The proof is similar to Theorem 4.1 since to prevent one color from appearing only once, Bob’s strategy is to duplicate all \(k\) colors in \(V(K_n)\) and to delay this duplication, Alice chooses as few colors as possible using colors that have already been duplicated. In that case, if Bob starts the game, Alice achieves that the first two colors are duplicated in the first five turns, delaying color duplication by one turn (see Figure 8). ◻
Now, we analyze the Conflict-Free Open Neighborhood \(k\)-coloring game. We refer to
Figure 9 and observe that
the two unique ways of CFON \(k\)-coloring a complete graph \(K_n\) are the following:
\(\bullet\,\,(CFON_1)\) all the \(k\) colors are chosen exactly twice when
coloring all the vertices, or
\(\bullet\,\,(CFON_2)\) at least two
colors are chosen exactly once.
Theorem 4.3. Alice wins the CFON \(k\)-coloring game on a complete graph \(K_n\), when she starts, if and only if one of the following statements holds:
\(n=2\) and \(k\geq 1\);
\(n=4\) and \(k\geq 2\);
\(n=3,5,6\) and \(k\geq 3\);
\(n\geq 7\) and \(k\geq\left \lceil{{\frac{n+7}{4}}}\right \rceil\).
Proof. Since for all \(v \in V(K_n)\) we have that \(|N(v)|=n-1\) so, in the first \(n-2\) turns, \(N(v)\) is not fully colored, for all \(v \in V(K_n)\).
If \(n\) is odd, only \((CFON_2)\) can be used to obtain a CFON \(k\)-coloring of \(K_n\). If \(n\) is even, both can be used: \((CFON_1)\) requires \(\frac{n}{2}\) colors to obtain a CFON \(k\)-coloring of \(K_n\), and \((CFON_2)\) only \(3\) colors. In Figure 9, we show a CFON \(k\)-coloring game of \(K_8\) with \(k=4\) using \((CFON_1)\), and \(k=3\) applying \((CFON_2)\).
So, if \(n\geq 8\), Alice reduces the number of colors needed to win with coloring \((CFON_2)\). Since \(n-2\geq 6\), in the first \(5\) turns, Alice chooses the same color with which she starts the game three times (no neighborhood is fully colored), discarding the possibility of each color appearing only two times to obtain a CFON \(k\)-coloring of \(K_n\).
So, in both cases, to prevent a color from appearing only once, Bob’s strategy is to duplicate all \(k\) colors in \(K_n\) and, to delay this duplication, Alice chooses as few colors as possible using colors that have already been duplicated.
We recall that, since Alice starts the game with a color \(c_1\) (and chooses this color in her next turn), in the second turn, Bob colors a vertex with a color \(c_2 \neq c_1\), to maximize the number of duplicated colors in the first four turns. Hence, he obtains two duplicated colors in the first four turns, With these strategies, for every \(4t\) turns they have used exactly \(t+1\) colors at least twice. Without loss of generality, we assume that Alice starts the game with color \(c_1\) and chooses this color in her first \(n-2\) turns.
If \(n\geq 7\) and \(k <\left \lceil{{\frac{n+7}{4}}}\right \rceil\), then there exists \(t\in\mathbb{N}\) such that \(4t<n-2\leq 4(t+1)\), so \(4t+2<n\leq 4(t+1)+2\). Therefore, \[k<\left \lceil{{\frac{n+7}{4}}}\right \rceil\leq\left \lceil{{\frac{4(t+1)+2+7}{4}}}\right \rceil=t+3.\]
Thus, \(k\leq t+2\) and, since \(|V(K_n)-2|>4t\), we have that: \((i)\) by the time Alice and Bob have colored \(4t\) vertices, they have already used all the \(k-1\) colors at least twice; \((ii)\) Alice chose color \(c_1\) at least three times, and the graph is not fully colored. Hence, Bob wins the game, since there are no two colors that can appear only once in \(K_n\).
Reciprocally, if \(n\geq 7\) and \(k\geq\left \lceil{{\frac{n+7}{4}}}\right \rceil\), we study four possible cases:
Case 1. Suppose that \(n=4t+3\) for some \(t \in \mathbb N\). In the \((4t)\)-th turn they have used exactly \(t+1\) colors at least twice. Since in the \((4t+1)\)-th turn Alice chooses the color \(c_1\), in order to obtain a CFON \(k\)-coloring of \(K_n\), in the \((4t+2)\)-th and \((4t+3)\)-th turns, by the legal coloring rule, they use two new colors that have not been chosen. Therefore, Alice wins if \[k\geq t+3= \left \lceil{{\frac{4t+10}{4}}}\right \rceil = \left \lceil{{\frac{4t+3+7}{4}}}\right \rceil = \left \lceil{{\frac{n+7}{4}}}\right \rceil.\]
Case 2. Suppose that \(n=4t+4\) for some \(t \in \mathbb N\). In the \((4t)\)-th turn they have used exactly \(t+1\) colors at least twice. In the \((4t+1)\)-th turn Alice chooses the color \(c_1\). In the \((4t+2)\)-th turn, Bob chooses a new color \(c_{t+2}\) (if there not exist such color, then Bob wins). In the turn \((4t+3)\)-th, Alice chooses the color \(c_1\) again. In the \((4t+4)\)-th turn, by the legal coloring rule, Bob is forced to use a new color \(c_{t+3}\) (if such color does not exist, then Bob wins). Thus, Alice wins if \[k \geq t+3 = \left \lceil{{\frac{4t+11}{4}}}\right \rceil=\left \lceil{{\frac{4t+4+7}{4}}}\right \rceil=\left \lceil{{\frac{n+7}{4}}}\right \rceil.\]
Case 3. If \(n=4t+5\) for some \(t \in \mathbb N\) then, in the \((4t+3)\)-th turn, Bob and Alice have used \(t+2\) colors such that \(t+1\) colors are used more than twice, and a single color is used only once. If in the \((4t+4)\)-th turn Bob does not use a new color, then Alice does it in the final turn. If Bob uses a new color, then Alice just needs to use color \(c_1\) again. In any case, Alice wins if \[k \geq t+3 = \left \lceil{{\frac{4t+12}{4}}}\right \rceil = \left \lceil{{\frac{4t+5+7}{4}}}\right \rceil=\left \lceil{{\frac{n+7}{4}}}\right \rceil.\]
Case 4. If \(n=4t+6\) for some \(t \in \mathbb N\) then, in the \((4t+4)\)-th turn, Alice and Bob have used exactly \(t+2\) colors at least twice. By the legal coloring rule, in the \((4t+5)\)-th turn Alice used a new color \(c_{t+3}\) (if there is such color), and Bob is forced to use a color \(c_{t+4}\) never used before (if it exists). Hence, Alice wins if \[k\geq t+4 = \left \lceil{{\frac{4t+14}{4}}}\right \rceil=\left \lceil{{\frac{4t+7+7}{4}}}\right \rceil=\left \lceil{{\frac{n+7}{4}}}\right \rceil.\] ◻
Theorem 4.4. Alice wins the CFON \(k\)-coloring game on a complete graph \(K_n\), when Bob starts, if and only if one of the following statements holds:
(a) \(n=2\) and \(k\geq 1\);
(b) \(n=4\) and \(k\geq 2\);
(c) \(n=3,5,6\) and \(k\geq 3\);
(d) \(n\geq 7\) and \(k\geq\left \lceil{{\frac{n+6}{4}}}\right \rceil\).
Proof. The proof is similar to Theorem 4.3 but, in this case, the first two colors are duplicated in the first five turns. ◻
A path \(P_n=(v_0,v_1,\ldots,v_{n-1})\) is a graph whose \(n\) vertices can be arranged in a linear sequence in such a way that two vertices are adjacent if and only if they are consecutive in the sequence. We call the vertices \(v_1, v_2,v_3,…,v_{n-2}\) as internal vertices of \(P_n\). In the next results, we prove that \(\chi^g_{CN}(P_n)=2\) and \[\chi^g_{ON}(P_n)=\begin{cases} 2 &, \mbox{ if } n\leq 7,\\ 3 &, \mbox{ if } n>7. \end{cases}\]
Theorem 5.1. Alice wins the CFCN \(k\)-coloring game on a path \(P_n=(v_0\), \(v_1\), \(\ldots,v_{n-1})\) on \(n\geq 2\) vertices with \(k \geq 2\) colors, independently of who starts playing.
Proof. Let \(P_n\) be a
path with \(n\geq 2\) and let \(c_1\), \(c_2\) and \(c_3\) be three different colors. If \(k=2\) then, by the legal coloring rule, the
only two strategies for Bob to win is by obtaining, on Alice’s turn, the
following colorings for subgraphs of \(P_n\). We refer to Figure 10 for an illustration of Bob’s
strategies 1 and 2.
\(\bullet\,\,(BS_1)\) coloring a
subgraph \(P_5=(v_i, v_{i+1}, v_{i+2},
v_{i+3}, v_{i+4})\), uniquely formed by internal vertices of
\(P_n\) , such that vertices \(v_i\), \(v_{i+1}\) are colored with a color \(c_1\); vertices \(v_{i+3}, v_{i+4}\) are colored with a color
\(c_2\); and the vertex \(v_{i+2}\) is uncolored; or
\(\bullet\,\,(BS_2)\) coloring the
subgraph \(P_4=(v_0, v_1, v_2, v_3)\)
(resp. \(P_4=(v_{n-4}, v_{n-3},
v_{n-2}\), \(v_{n-1})\)), such
that the vertex \(v_0\) (resp. vertex
\(v_{n-1}\)) is colored with a color
\(c_1\), and the vertices \(v_2\) and \(v_3\) (resp. vertices \(v_{n-4}\) and \(v_{n-3}\)) are colored with a color \(c_2\), and vertex \(v_1\) (resp. \(v_{n-2}\)) is uncolored.
We prove that, Alice’s strategy is to color any vertex adjacent to the vertex colored by Bob in the previous turn, with a color different from the one that Bob used. In case all the vertices adjacent to the vertex colored by Bob have already been colored, it is enough for Alice to choose any uncolored vertex \(w\) adjacent to a colored vertex \(v\), and to color \(w\) with a color that is different to the one used in \(v\).
If \(n=2,3\), Alice wins, since the strategies \((BS_1)\) and \((BS_2)\) need at least four vertices.
For \(n=4\), without loss of generality, we analyze the game when Bob starts coloring \(v_0\) or \(v_1\). If Bob decides to start the game by coloring \(v_0\) with a color \(c_1\) then, on the second turn, Alice colors \(v_1\) with a color \(c_2\). Hence, no \(P_4\) subgraph can be colored as in \((BS_2)\). On the other hand, if Bob starts the game by coloring the vertex \(v_1\) with a color \(c_1\) then, on the next turn, Alice either colors the vertex \(v_0\) or colors the vertex \(v_2\) with a color \(c_2\). Again, no \(P_4\) subgraph can be colored as in \((BS_2)\). In both cases, Alice wins.
For \(n=5, 6\), Bob’s unique strategy is to consider subgraphs \(P_4\) \((BS_2)\). Indeed, strategy \((BS_1)\) can not be used because \(P_5\) or \(P_6\) do not have five internal vertices. Without loss of generality, suppose that Bob tries to win by obtaining a subgraph \(P_4=(v_0, v_1, v_2, v_3)\) (it is analogous for \(P_4=(v_{n-4}, v_{n-3}, v_{n-2}, v_{n-1})\)). If Bob starts coloring any vertex \(v_i\), with \(0\leq i\leq 2\) (resp. \(v_3\)) then, in the next turn, Alice colors an adjacent vertex (resp. vertex \(v_2\)) with a different color. Thus, no \(P_4=(v_0, v_1, v_2, v_3)\) subgraph can be colored as in \((BS_2)\), and Alice wins.
Let \(n \geq 7\). First, suppose that Bob tries to win obtaining a subgraph \(P_5=(v_i\), \(v_{i+1}\), \(v_{i+2}\), \(v_{i+3}\), \(v_{i+4})\), that has the coloring \((BS_1)\). Assume that it is Bob’s turn and he looks for a subgraph \(P_5\), that has only \(v_i\) colored with a color \(c_1\) and \(v_{i+4}\) colored with \(c_2\). We observe that if any internal vertex \(v_j\), with \(j\in\{i+1, i+2, i+3\}\), on the subgraph \(P_5\) is already colored then, by Alice’s strategy, no \(P_5=(v_i\), \(v_{i+1}\), \(v_{i+2}\), \(v_{i+3}\), \(v_{i+4})\) subgraph can be colored as in \((BS_1)\) (there exist two adjacent vertices of different colors in \(P_5\)), and Alice wins. Thus, in his turn, Bob tries to color \(v_{i+1}\) or \(v_{i+3}\), with the same color of its adjacent vertex. In the next turn, Alice colors the vertex \(v_{i+2}\) and wins. If Bob tries to win by obtaining a subgraph \(P_4\) with the coloring \((BS_1)\), the proof that Alice wins is similar to the one used on the paths of order \(5\) or \(6\).
It may seem that since Alice wins when Bob starts the game, if she starts and follows the same strategy, then she wins. However, this is not the case. Assume that Bob follows strategy \((BS_2)\) and tries to win on the subgraph \(P_4=(v_0, v_1, v_2, v_3)\). If Alice starts coloring vertex \(v_2\) with a color \(c_1\), then Bob colors \(v_3\) with the same color \(c_1\). Following her strategy, Alice colors \(v_4\) with a different color. Now, Bob colors \(v_0\) with color \(c_2\), and he wins.
In the same way, if Bob finds a subgraph \(P_5=(v_i, v_{i+1}, v_{i+2}, v_{i+3}, v_{i+4})\) such that \(v_i\) and \(v_{i+1}\) (resp. \(v_{i+3}\) and \(v_{i+4}\)) are colored with the same color \(c_1\) and the remaining vertices in \(P_5\) are uncolored (possible if Alice starts the game), then he colors \(v_{i+4}\) (resp. \(v_i\)) with a different color \(c_2\). If in the next turn, Alice colors the adjacent vertex to \(v_{i+4}\) (resp. \(v_i\)) that is not in this subgraph \(P_5\), then Bob colors the vertex \(v_{i+3}\) (resp. \(v_{i+1}\)) with the color \(c_2\), and he wins.
In order to avoid that, Alice starts the game coloring \(v_1\) or \(v_{n-2}\) of \(P_n=(v_0\), \(v_1\), \(\ldots\), \(v_{n-1})\) (preventing Bob from winning in subgraphs \(P_4\) or \(P_5\)). From the third turn onward, she colors the adjacent vertices of those Bob colored (as in the case Bob started the game). Therefore, Alice wins the game with \(k=2\) colors.
If \(k>2\), then Alice colors either vertex \(v_{i+2}\) on subgraph \(P_5\); or vertex \(v_1\) (or \(v_{n-2}\)) on subgraph \(P_4\) with a color \(c_3\), winning the game. ◻
Now, we analyze the CFON \(k\)-coloring game on \(P_n\). We show in Figure 11 the unique strategy for Bob
to win the CFON \(k\)-coloring game in
\(P_n\).
\(\bullet\,\,(BS_3)\) coloring a
subgraph \(P_5=(v_i, v_{i+1}, v_{i+2},
v_{i+3}, v_{i+4})\), such that vertex \(v_i\) is colored with a color \(c_1\) and vertex \(v_{i+4}\) is colored with a color \(c_2\), \(c_1\not
= c_2\).
Theorem 5.2. Bob wins the CFON \(k\)-coloring game on a path \(P_n\), when Alice starts, if and only if \(n>7\) and \(k=2\).
Proof. Let \(P_n=(v_0,v_1,\ldots,v_{n-1})\) be a path with \(n\geq 3\), let \(c_1\), \(c_2\) and \(c_3\) be three different colors. If \(k=2\), the only way for Bob to win is considering, on Alice’s turn, a subgraph \(P_5=(v_i, v_{i+1}, v_{i+2}, v_{i+3}, v_{i+4})\), such that the vertex \(v_i\) is colored with a color \(c_1\), and the vertex \(v_{i+4}\) with a color \(c_2\). In that case, by the legal coloring rule, vertex \(v_{i+2}\) cannot be colored either with \(c_1\), because of \(N(v_{i+1})\); nor with \(c_2\), because of \(N(v_{i+3})\).
If \(n\in\lbrace 2,3,4\rbrace\) it is immediate that Alice wins the game. If \(n=5\) then Alice starts coloring the vertex \(v_2\), and wins. If \(n=6\) then Alice starts coloring \(v_2\) (resp. \(v_3\)) and, in the third turn, she colors \(v_3\) (resp. \(v_2\)), and wins.
If \(n=7\), then Alice starts coloring the vertex \(v_3\). By the legal coloring rule, Bob cannot color vertices \(v_1\) and \(v_5\) with different colors. Thus, in the next turn, Bob colors \(v_i\), \(i\in\{0, 2\}\) (resp. \(i\in\{4,6\}\)). Alice colors \(v_{i+4}\) (resp. \(v_{i-4}\)) with the same color that Bob used. Alice wins because it is not possible to apply \((BS_3)\) in one of the three subgraphs \(P_5\).
If \(n>7\), independently of which vertex \(v_i\) (resp. \(v_{i+4}\)) Alice chooses to color in her first turn, Bob can always find a subgraph \(P_5=(v_i, v_{i+1}, v_{i+2}. v_{i+3}, v_{i+4})\), and color \(v_{i+4}\) (resp. \(v_{i}\)) with a different color.
Now assume \(k>2\). If \(n\in\{1,2,3\}\) then it is immediate that Alice wins the game. If \(n\geq 4\), then Alice colors vertex \(v_{i+2}\) of the subgraphs \(P_5=(v_i, v_{i+1}, v_{i+2}. v_{i+3}, v_{i+4})\), with a color \(c_3\), winning the game. ◻
Theorem 5.3. Bob wins the CFON \(k\)-coloring game on a path \(P_n\), when he starts the game, if and only if \(n>8\) and \(k=2\).
Proof. If \(n\in\{2,3,4\}\) then it is immediate that Alice wins the game. If \(n=5\), then Alice colors vertex \(v_{2}\), and wins. For \(n\in\{6,7,8\}\), if Bob starts coloring a vertex \(v_j\), then Alice colors either vertex \(v_{j-4}\), if \(j> 3\); or vertex \(v_{j+4}\), if \(j< 3\). In both cases, she prevents Bob to win the game.
If \(n>8\) and \(k=2\) then Bob starts coloring vertex \(v_4\) with a color \(c_1\). We note that there are two subgraphs \(P_5\) such that \(v_4\) is either the last or the first vertex. Now, independently of which vertex Alice colors, Bob wins the game.
Now, assume that \(k>2\). If \(n\in\{1,2,3\}\), then it is immediate that Alice wins the game. If \(n>3\), then Alice colors the vertex \(v_{i+2}\) of all subgraphs \(P_5\) with a color \(c_3\), ensuring her victory in the game. ◻
A cycle \(C_n=(v_0,v_1,\ldots,v_n)\), with \(n\geq 3\) and \(v_0=v_n\) is a graph whose \(n\) vertices can be arranged in a cyclic sequence in a way that two vertices are adjacent if and only if they are consecutive in the sequence. Next, we prove that \(\chi^g_{CN}(C_n)=2\) and \(\chi^g_{ON}(C_n)=3\).
The approach for cycles follows a similar pattern as with paths.
However, Bob’s victory is restricted on applying the strategy \((BS_1)\). As previously, Alice adopts a
strategy where she colors any vertex adjacent to Bob’s previously
colored vertex with a distinct color. In the event that all adjacent
vertices to Bob’s colored vertex have already been colored, Alice can
ensure her advantage by selecting any uncolored vertex, denoted as \(w\), that is adjacent to a previously
colored vertex \(v\), and coloring
\(w\) with a different color than \(v\).
Theorem 6.1. Alice wins the CFCN \(k\)-coloring game on a cycle \(C_n\) with \(k \geq 2\) colors, independently of who starts playing.
Proof. Let \(k=2\). It is easy to see that Alice wins the game for \(n\in \{3,4\}\). Let \(n=5\) and consider that Alice starts the game coloring \(v_0\) with color \(c_1\). Independently of the vertex colored by Bob in the second turn, Alice colors an uncolored vertex \(v_2\) or \(v_3\) with color \(c_1\).
Let \(n\geq 6\). Assuming Bob is the first player, at some point in the game, he attempts to find a subgraph \(P_5 = (v_i, v_{i+1}, v_{i+2}, v_{i+3}, v_{i+4})\) in which \(v_i\) is colored with color \(c_1\), \(v_{i+4}\) is colored with \(c_2\) (\(c_1\neq c_2\)), and the remaining vertices of \(P_5\) are uncolored. Similarly to paths, Alice’s strategy is to color (on the subgraph \(P_5\)) either vertex \(v_{i+2}\) or the vertices \(v_{i+1}\) (resp. \(v_{i+3}\)) with a different color from that used for \(v_i\) (resp. \(v_{i+4}\)).
If Alice starts the game, her strategy has a slight variation. Consider the vertex \(v_i\) colored by Bob in his last turn as the reference vertex. If there exist two adjacent colored vertices with the same color in the clockwise direction of \(v_i\), then Alice colors the vertex \(v_{i+1}\). However, if these two vertices are in the counterclockwise direction, Alice colors the vertex \(v_{i-1}\). Otherwise, if there exist no adjacent colored vertices with the same color in either the clockwise or counterclockwise direction, Alice simply colors any of the adjacent vertices.
This variant is used because, if Alice doesn’t have a preference for coloring the adjacent vertex based on the direction of the adjacent colored vertices, it could potentially allow Bob to win the game. Indeed, suppose that Alice starts the game coloring a vertex \(v_i\) with a color \(c_1\). Bob colors a vertex \(v_{i+1}\) with color \(c_1\). Now, Alice colors \(v_{i+2}\) with a different color \(c_2\). If there exist at least three uncolored vertices \(\{v_{i-1}, v_{i-2}, v_{i-3}\}\) adjacent to \(v_{i}\), then Bob tries \((BS_1)\) on the subgraph \(P_5=(v_{i-3}, v_{i-2}, v_{i-1}, v_{i}, v_{i+1})\), and colors \(v_{i-3}\) with a color \(c_2\). With the variant strategy, Alice colors the adjacent vertex \(v_{i-2}\) with color \(c_1\), and wins the game.
For \(k>2\), the idea is the same as in the Theorem 5.1. Therefore, Alice always wins the game. ◻
Since the results for the game on \(C_3\) are addressed by Theorems 4.3 and 4.4, we now consider
the CFON \(k\)-coloring game on \(C_n\) for \(n
\geq 4\) and \(k \geq 2\).
Theorem 6.2. Bob wins the CFON \(k\)-coloring game on a cycle \(C_n\), \(n> 4\), when Alice starts the game, if and only if \(k=2\).
Proof. Again, the strategy applied to cycles \(C_n\), with \(n>4\), is similar to that of paths. If \(k=2\), then Bob can only win by considering a subgraph \(P_5=(v_i\), \(v_{i+1}\), \(v_{i+2}\), \(v_{i+3}\), \(v_{i+4})\), where the vertex \(v_i\) is colored with a color \(c_1\) and the vertex \(v_{i+4}\) is colored with a different color \(c_2\). The proof follows a similar approach to Theorem 5.2. Regardless of the vertex Alice chooses to color in the first turn, Bob can always find a subgraph \(P_5=(v_i, v_{i+1}, v_{i+2}, v_{i+3}, v_{i+4})\) where \(v_i\) is the vertex colored by Alice, and Bob can color \(v_{i+4}\) with another color, winning the game.
Conversely, if \(k>2\), Alice can always color the vertex \(v_{i+2}\) in all subgraphs \(P_5\) with a color \(c_3\), such that \(c(v_i)\not=c(v_{i+4})\not=c_3\). Therefore, she wins the game. ◻
Theorem 6.3. Bob wins the CFON \(k\)-coloring game on a cycle \(C_n\), \(n>4\), when he starts the game, if and only if \(n \neq 8\) and \(k=2\).
Proof. If \(n=8\) then, whenever Bob colors a vertex \(v_j\), Alice colors the vertex \(v_{j+4\text{ (mod }n\text{)}}\) with the same color used by Bob. Let \(P_5=(v_i, v_{i+1}, v_{i+2}, v_{i+3}, v_{i+4})\) be a subgraph of \(C_n\). If \(k>2\), then Alice can always color the uncolored vertices \(v_{i+2}\) of all subgraphs \(P_5\) with a color \(c_3\), such that \(c(v_i)\not=c(v_{i+4})\not=c_3\). In both cases, Alice wins the game.
Conversely, assume that \(n \neq 8\) and \(k=2\). If \(n=6\) and Bob starts coloring the vertex \(v_j\), Alice can not color the vertex \(v_{j+4\text{ (mod }n\text{)}}\) (resp. \(v_{j+2\text{ (mod }n\text{)}}\)) with the same color, otherwise, the open neighborhood of \(v_{j+5\text{ (mod }n\text{)}}\) (resp. \(v_{j+1 \text{ (mod }n\text{)}}\)) would be monochromatic. Hence, Bob wins the game. In the cases \(n \notin \{6,8\}\), regardless of which vertex Alice chooses to color in the second turn, Bob can always find, in the third turn, a subgraph \(P_5\) that includes either \(v_i\) or \(v_{i+4}\) as the vertex colored by Alice. ◻
The windmill graph \(W(n,p)\) with \(n\geq 2\), \(p\geq 2\), is composed by the disjoint union of \(p\) complete graphs \(K_{n}\) of order \(n\) joined with a single vertex \(u\) called the universal vertex. We refer to Figure 12 for an example of the windmill graph \(W(2,p)\), which is also known as friendship or Dutch windmill graph.
Similarly, a generalized windmill graph \(W(N,p)\), with \(N = \{n_1, n_2, \ldots, n_p\}\), \(p\geq 2\), is composed by the disjoint union of \(p\) complete graphs \(K_{n_i}\) of order \(n_i\), with \(n_i\geq 2\), for \(1 \leq i \leq p\), joined with a single universal vertex \(u\). See an example of \(W(\{3,2,4,2\},4)\) in Figure 13.
In this section, we study the CFCN \(k\)-coloring game on generalized windmill graphs. Let \(c:V(W(N,p)) \to \{c_1,c_2\ldots,c_k\}\) be a \(k\)-vertex coloring of \(W(N,p)\), where \(\lbrace c_1,c_2,…,c_k\rbrace\) represents a set of \(k\) different colors. Let \(c^{-1}(c_i)\) be the subset of vertices assigned to color \(c_i\), \(i\in \{1, \dots, k\}\) (color class). We observe that in a CFCN \(k\)-coloring of \(W(N,p)\), one of the following statements holds:
the color of the universal vertex appears only once;
the color of the universal vertex is duplicated but, for every \(1 \leq i \leq p\), at least one color \(c_i\) appears exactly once in \(K_{n_i}\) and there exists \(1 \leq j \leq p\) such that \(|c^{-1}(c_j)|=1\).
Again, Bob’s strategy is to duplicate each of the \(k\) colors that are used and, to delay this duplication, Alice chooses as few colors as possible using colors that have already been duplicated.
Lemma 7.1. If Alice tries to use as few colors as possible in the CFCN \(k\)-coloring game on \(W(N,p)\), then Bob can always duplicate the color of the universal vertex \(u\) in the first \(4\) turns.
Proof. We prove this result considering \(W(2,2)\), since \(W(2,2)\) is a induced subgraph of \(W(N,p)\) for any arbitrary windmill graph \(W(N,p)\), \(N\geq 2\) and \(p\geq 2\). We refer to Figures 14 and 15.
If Alice starts the game and colors vertex \(u\) with \(c_1\), then Bob colors any vertex on \(W(2,2)\) with \(c_2\). No matter which vertex Alice colors with \(c_1\) (resp. \(c_2\)), in the fourth turn, Bob colors any vertex with \(c_2\) (resp. \(c_1\)). If Alice starts the game and colors a vertex \(v\not = u\) with \(c_1\) then, in the next turn, Bob colors \(u\) with \(c_2\). The case is similar if Bob starts the game. In any case, Bob duplicates the first two colors in the first four turns. ◻
By Lemma 7.1, we have the following result:
Lemma 7.2. Assume that Alice tries to use as few colors as possible and Bob duplicates the color of the universal vertex in the CFCN \(k\)-coloring game on \(W(N,p)\). If there exist at least two uncolored vertices in \(W(N,p)\), then Bob always duplicates a color that appeared only once.
Proof. Without loss of generality, assume that there are only two uncolored vertices \(w\) and \(w'\), and that \(c(v_i)\) appears only once. By Lemma 7.1, since the color of the universal vertex \(u\) is duplicated in the first four turns, then \(v_i\in K_{n_i}\) and \(w\not =w'\not =u\).
If \(w,w'\in V(K_{n_j})\) (\(K_{n_j}\) is not fully colored), then one of them can be colored with \(c(v_i)\). However, if they are in different \(K_{n_j}\), then it is sufficient to color with \(c(v_i)\) the uncolored vertex in \(K_{n_j}\) with \(i\not=j\). ◻
To ensure that both players play optimally, we also need to verify
the following result:
Lemma 7.3. Assume that Bob duplicates the color of the universal vertex in the CFCN \(k\)-coloring game on \(W(N,p)\). If there exist at least two uncolored vertices in \(W(N,p)\), then Alice always chooses either the same color or any of the colors that have already been chosen at least twice.
Proof. Without loss of generality, we assume that there are only two uncolored vertices. Furthermore, suppose that it is Alice’s turn, she has chosen the same color \(c_1\) in all previous turns, and, due to the legal coloring rule, she is now forced to select a new color. We claim that Alice chooses a duplicated color. If the two uncolored vertices are on the same \(K_{n_i}\), then one of them can be colored with \(c_1\) (\(K_{n_i}\) is not fully colored), a contradiction. Thus, one uncolored vertex is in \(K_{n_i}\) and the other one is in \(K_{n_j}\), \(1\leq i,j \leq p\), \(i\not = j\). If color \(c_1\) cannot be chosen, by the legal coloring rule, either \(c_1\) appears only once and the remaining colors appear at least twice in \(K_{n_i}\), or every color appears at least twice in \(K_{n_i}\). In any case, since Bob chooses a new color every time he achieves a color duplication, we have that the colors duplicated in some \(K_{n_i}\) are not duplicated in another \(K_{n_j}\), for \(1\leq i,j \leq p\), \(i\not = j\). So, there always exists a duplicated color in \(K_{n_i}\) (resp. \(K_{n_j}\)) that can be chosen by Alice in \(K_{n_j}\) (resp. \(K_{n_i}\)). ◻
The next two results show that \[\chi_{CN}^g(W(N,p))=\left\lceil{\frac{|V(W(N,p))|+4}{4}}\right\rceil.\]
Theorem 7.4. Alice wins the CFCN \(k\)-coloring game on a generalized windmill graph \(W(N,p)\), when she starts, if and only if \[k>\left\lceil{\frac{|V(W(N,p))|}{4}}\right\rceil.\]
In particular, since \(|V(W(n,p))|=n\cdot p +1\), she wins the CFCN \(k\)-coloring game on a windmill graph \(W(n,p)\), when she starts, if and only if \(k>\left\lceil{\frac{n\cdot p+1}{4}}\right\rceil\).
Proof. By Lemmas 7.2 and 7.3, before coloring the last vertex, for every \(4t\) turns Alice and Bob have used exactly \(t+1\) colors, and each of them has been used at least twice (the proof is by induction on \(t\)).
Since \(|W(N,p)|>4\), there exists \(t\in\mathbb{N^*}\) such that \(4t<|W(N,p)|\leq 4(t+1)\). If \(k \leq\) \(\left \lceil{{\frac{|W(N,p)|}{4}}}\right \rceil\), then
\[k\leq\left \lceil{{\frac{|W(N,p)|}{4}}}\right \rceil\leq\left \lceil{{\frac{4(t+1)}{4}}}\right \rceil=t+1,\] and we have that by the time Alice and Bob have colored \(4t\) vertices, they have already used all the \(k\) colors at least twice. Furthermore, since \(4t<|W(N,p)|\), the graph is not fully colored. Hence, Bob wins the game because there exists no color available to use only once.
Reciprocally, if \(k > \lceil{\frac{|W(N,p)|}{4}} \rceil\), since \(4t<|W(N,p)|\leq 4(t+1)\), then \(t<\lceil{\frac{|W(N,p)|}{4}} \rceil\leq t+1\). Thus, \(t+1=\lceil{\frac{|W(N,p)|}{4} \rceil}<k\). So, \(k\geq t+2\) and, to duplicate \(t+2\) colors, Bob needs at least \(4(t+1)+1\) vertices. Since \(|W(N,p)|\leq 4(t+1)\), Alice wins the game. ◻
Now we show that, when Bob starts the CFCN \(k\)-coloring game on a generalized windmill graph \(W(N,p)\), Alice requires one fewer color to win.
Theorem 7.5.
Alice wins the CFCN \(k\)-coloring game on a generalized windmill graph \(W(N,p)\), when Bob starts, if and only if \[k>\left\lceil{\frac{|W(N,p)|-1}{4}}\right\rceil.\]
In particular, since \(|V(W(n,p))|=n\cdot p +1\), she wins the CFCN \(k\)-coloring game on a windmill graph \(W(n,p)\), when Bob starts, if and only if \(k>\left\lceil{\frac{n\cdot p}{4}}\right\rceil\).
Proof. The proof is similar to Theorem 7.4. Again, to prevent one color from appearing only once, Bob’s strategy is to duplicate all \(k\) colors in \(W(N,p)\), and to delay this duplication, Alice chooses as few colors as possible using colors that have already been duplicated. If Bob starts the game, then the first two colors are duplicated in the first five turns, delaying color duplication by one turn. ◻
In this work, we study the Conflict-Free \(k\)-coloring games on classic graph classes such as stars, complete graphs, paths, cycles, and windmill graphs and their generalization. In each of them, we show strategies that determine the least number of colors necessary for Alice to win the game.
We recall that the Closed (resp. Open) Neighborhood Conflict-Free game Chromatic Number of \(G\), denoted by \(\chi^g_{CN}(G)\) (resp. \(\chi^g_{ON}(G)\)), is the minimum number \(k\) of colors necessary for Alice to have a winning strategy for the CFCN (resp. CFON) \(k\)-coloring game on \(G\), independently of who starts the game.
| Graph | \(\chi_{CN}(G)\) | \(\chi^g_{CN}(G)\) | \(\chi_{ON}(G)\) | \(\chi^g_{ON}(G)\) | Theorems |
| [0.5em] | |||||
| [-0.7em] \(S_n-1\) | \(2\) | \(2\) | \(2\) | \(\left \lceil{{\frac{n-1}{4}}}\right \rceil+1\) | 3.1,3.2,3.3 |
| [0.4em]\(K_2\) | \(1\) | \(1\) | \(1\) | \(1\) | 4.1,4.2,4.3,4.4 |
| \(K_4\) | \(2\) | \(2\) | \(2\) | 2 | 4.1,4.2,4.3,4.4 |
| \(K_3\), \(K_5\), \(K_6\) | \(3\) | \(3\) | \(3\) | \(3\) | 4.1,4.2,4.3,4.4 |
| \(K_n\ (n\geq 7)\) | \(2\) | \(\left \lceil{{\frac{n}{4}}}\right \rceil+1\) | 3 | \(\left \lceil{{\frac{n+7}{4}}}\right \rceil\) | 4.1,4.2,4.3,4.4 |
| \(P_n\ (n\leq 7)\) | \(2\) | \(2\) | \(2\) | \(2\) | 5.1,5.2,5.3 |
| \(P_n\ (n > 7)\) | \(2\) | \(2\) | \(2\) | \(3\) | 5.1,5.2,5.3 |
| \(C_n\) | \(2\) | \(2\) | \(2\) | \(3\) | 6.1,6.2,6.3 |
| \(W(N,p)\) | \(2\) | \(\left \lceil{{\frac{|V(W(N,p))|+4}{9}}}\right \rceil\) | – | – | 7.4,7.5 |
In Table 1, we show our results on the Conflict-free \(k\)-coloring game comparing \(\chi_{CN}(G)\), \(\chi^g_{CN}(G)\), \(\chi_{ON}(G)\) and \(\chi^g_{ON}(G)\). We remark that it may seem that if Alice wins when Bob starts the game, then she also wins when she starts the game. However, this is not always true. In fact, since Alice’s general strategies are based on preventing Bob from achieving his general strategies, when Alice starts, her turn can eventually contribute to improve Bob’s strategy to win the game. For example, in the CFCN \(2\)-coloring game on the complete graph \(K_5\), Alice wins when Bob starts the game, and loses when she starts the game (see Theorem 4.1 and Theorem 4.2). Sometimes it is possible to prevent that by improving Alice’s strategies, as it occurs in the CFCN \(2\)-coloring game on paths \(P_n\) and cycles \(C_n\) with \(n\geq 5\), (see Theorem 5.1 and Theorem 6.1).
Finally, the general strategies lead us to pose the following question:
Question 8.1(Monotonicity).Assume that Alice wins the CFCN \(k\)-coloring game (resp. CFON \(k\)-coloring game) on \(G\). Does she win the CFCN (resp. CFON) \((k+1)\)-coloring game on \(G\) when the same player starts the game?
All authors contributed equally to the research, analysis, and writing of this paper.
This work was partially supported by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001; the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) 311260/2021-7, 313797/2020-0; and the Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ) Processo SEI-260003/014835/2023, E-26/210.649/2023.
All authors declare that they have no conflicts of interest.
There is no conflict of interest related to this work.