Conflict-free coloring games

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. 

Proof. Since $N(v_0)=V(S_{n-1})\setminus \{v_0\}$ and $N(v)=v_0$ for every $v\ne 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)|\le 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)|\le 4(t+1)+1$, and since $|N(v_0)|=n-1$, we have that $4t+1<n-1\le 4(t+1)+1$.

Suppose that $k\le \lceil \frac{n-2}{4}\rceil$. Thus, we have that $$k\le \lceil \frac{n-2}{4}\rceil \le \lceil \frac{4(t+1)}{4}\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\le 4(t+1)$, then $t<\lceil \frac{n-2}{4}\rceil \le t+1$. Thus, $t+1=\lceil \frac{n-2}{4}\rceil <k$. So, $k\ge 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)|\le 4(t+1)+1$, Alice wins the game. 

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. 

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\ne 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\le$ $\lceil \frac{n}{4}\rceil$ and $n>4$. Thus, there exists $t\in \mathbb{N}$ such that $4t<n\le 4(t+1)$. Therefore, $$k\le \lceil \frac{n}{4}\rceil \le \lceil \frac{4(t+1)}{4}\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\le 4(t+1)$, we have that $t<\lceil \frac{n}{4}\rceil \le t+1$, and so $\lceil \frac{n}{4}\rceil =t+1$. Thus, $k>\lceil \frac{n}{4}\rceil \ge t+2$ and Bob needs at least $4(t+1)+1$ vertices to duplicate $t+2$ colors. Hence, Alice wins since $|N(v)|\le 4(t+1)$. 

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). 

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 $(CFO{N}_2)$ can be used to obtain a CFON $k$-coloring of $K_n$. If $n$ is even, both can be used: $(CFO{N}_1)$ requires $\frac{n}{2}$ colors to obtain a CFON $k$-coloring of $K_n$, and $(CFO{N}_2)$ only $3$ colors. In Figure 9, we show a CFON $k$-coloring game of $K_8$ with $k=4$ using $(CFO{N}_1)$, and $k=3$ applying $(CFO{N}_2)$.

So, if $n\ge 8$, Alice reduces the number of colors needed to win with coloring $(CFO{N}_2)$. Since $n-2\ge 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\ne 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\ge 7$ and $k<\lceil \frac{n+7}{4}\rceil$, then there exists $t\in \mathbb{N}$ such that $4t<n-2\le 4(t+1)$, so $4t+2<n\le 4(t+1)+2$. Therefore, $$k<\lceil \frac{n+7}{4}\rceil \le \lceil \frac{4(t+1)+2+7}{4}\rceil =t+3.$$

Thus, $k\le 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\ge 7$ and $k\ge \lceil \frac{n+7}{4}\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\ge t+3=\lceil \frac{4t+10}{4}\rceil =\lceil \frac{4t+3+7}{4}\rceil =\lceil \frac{n+7}{4}\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\ge t+3=\lceil \frac{4t+11}{4}\rceil =\lceil \frac{4t+4+7}{4}\rceil =\lceil \frac{n+7}{4}\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\ge t+3=\lceil \frac{4t+12}{4}\rceil =\lceil \frac{4t+5+7}{4}\rceil =\lceil \frac{n+7}{4}\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\ge t+4=\lceil \frac{4t+14}{4}\rceil =\lceil \frac{4t+7+7}{4}\rceil =\lceil \frac{n+7}{4}\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. 

Proof. Let $P_n$ be a path with $n\ge 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 (B{S}_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 (B{S}_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 $(B{S}_1)$ and $(B{S}_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 $(B{S}_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 $(B{S}_2)$. In both cases, Alice wins.

For $n=5,6$, Bob’s unique strategy is to consider subgraphs $P_4$ $(B{S}_2)$. Indeed, strategy $(B{S}_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\le i\le 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 $(B{S}_2)$, and Alice wins.

Let $n\ge 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 $(B{S}_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 $(B{S}_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 $(B{S}_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 $(B{S}_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$, $\dots$, $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. 

Proof. Let $P_n=(v_0,v_1,\dots ,v_{n-1})$ be a path with $n\ge 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 \{2,3,4\}$ 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 $(B{S}_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\ge 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. 

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. 

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\ge 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\ne 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 $(B{S}_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. 

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)\ne c(v_{i+4})\ne c_3$. Therefore, she wins the game. 

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)\ne c(v_{i+4})\ne c_3$. In both cases, Alice wins the game.

Conversely, assume that $n\ne 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.