Graph theory partitioning game

Question

Players Ruby and Bob are given an undirected graph and a number $N$. First Ruby colors $N$ vertices red, then Bob colors $N$ vertices blue (they must be distinct from Ruby's choices). Afterward, all other points on the graph are given the color of whichever color they are closest to (shortest path) with ties left blank. The player with more of their color on the resulting graph wins.

Can the first player always win (or tie)?

Some context: This problem arose for me out of a mobile puzzle game. My knowledge in graph theory is pretty minimal, so I don't have much machinery to solve it (but I have spent a while with small graphs, always able to find an unbeatable strategy for the first player). My thoughts so far are to mark points as having an advantage in comparison to their neighbors, the maximum of which I'd guess provides a win with N=1. For higher N though the dynamics get much more challenging for me to express. There seems to be an aspect of even-spacing which I'm not sure how to formalize (perhaps it's picking vertices which minimize their shortest distance to any point).

Also if anyone has heard of a similar problem before (specifically related to coloring a graph based on the shortest path to a colored vertex) or has references I'd be happy to read them, but was unable to find much since I'm not certain what to search for.

Answer 1

I believe that the first player cannot always guarantee a tie, even when $N=1$. Some observations:

• Given a graph $G$ and a vertex subset $X \subset V(G)$, we can always modify $G$ so that the players are forced to choose a vertex in $X$: add a huge independent set $I$ to $G$ and make all the vertices in $I$ adjacent only to the vertices in $X$, so that if one player plays outside $X$ and the other plays inside it, then the player inside $X$ grabs all vertices in $I$ and wins even if the other player gets everything else.

• This trick also lets us assign nonnegative integer weights to the edges, and calculate distances according to the weights: subdivide each edge an appropriate number of times, and choose our subset $X$ so that the internal vertices of the subdivided edges aren't feasible to play in. (Edit: As originally written this doesn't quite work, because the players in the modified graph would score points for the subdivided edges, but I think it can be made to work if you "blow up" the real vertices into large cliques or large independent sets, so that the value of getting one more "real vertex" far exceeds the value of the new vertices inside all the subdivided edges. This transformation doesn't quite preserve the rules of the game: in the transformed graph, Bob is essentially allowed to pick a vertex already chosen by Alice, so the transformed graph is friendlier to Bob than the original graph, but if the point is to come up with a graph where Bob can guarantee a win, then this is not a problem for us.)

Once you've done these tricks, I think you can create a rock-paper-scissors scenario using the complete bipartite graph $K_{3,3}$. Say that the three vertices one partite set are $R,P,S$ and that the three vertices of the other set are $X,Y,Z$. The vertex $R$ has weights $1,2,3$ to $X,Y,Z$ respectively; $P$ has weights $3,1,2$, and $S$ has weights $2,3,1$. The players are only allowed to play in $\{R,P,S\}$, via the above tricks.

Now, if Alice picks $R$, then Bob picks $P$ and gets $Y,Z$ versus Alice's $X$. ($S$ is equidistant to both $R$ and $P$). If Alice picks $P$, Bob picks $S$ and gets $X,Z$ versus Alice's $Y$. If Alice picks $S$, Bob picks $R$ and gets $X,Y$ versus Alice's $Z$.

Answer 2

I can prove that for the first player (Ruby) is possible not to lose in some simple cases for the given graph $G$ with $n$ vertices.

1. Domination number $\gamma(G)\le N$. Indeed, in this case at her move the first player can assure that the red vertices constitute a dominating set. Then after the second player move only $N$ vertices colored by him will become blue, because any not red vertex has a red neighbor, so if it was not colored by the second player then it becomes red if it has no blue neighbor or remains blank otherwise.

2. The graph $G$ is a tree and $N=1$. By Jordan Theorem from 1869 (which I proved independently few hours ago :-) ), $G$ has a vertex $v$ whose removal disconnects the tree into components of size at most $n/2$. So if the first player color the vertex $v$, the second player after his move will make blue only vertices from one of the connected components, whose size is at most $n/2$. The remaining vertices will become red.

3. The graph $G$ is a cycle. Let the first player color clockwise vertices $v_1,\dots, v_N,v_{N+1}=v_1$ assuring that their removal disconnects the cycle into components whose sizes differs by at most $1$. Let these sizes be $l$ and $l+1$. For any $i<N$ denote the clockwise path (without its second endpoint) from a vertex $v_i$ to a vertex $v_{i+1}$ by $[v_i,v_{i+1})$. Consider a component $C$ bounded by vertices $v_i$ and $v_{i+1}$. If the second player color one vertex $v$ in $C$, then $C$ with its two red boundary vertices will be split into two paths $v_i,\dots, v$ and $v,\dots, v_{i+1}$ with the endpoints of different colors. By symmetry, after the final coloring each of them will have equal number of red and black vertices. But here the blue vertex $v$ was counted two times, as a endpoint of each of the paths. Taking this into account we see that the second player obtain no gain at the clockwise path $[v_i,v_{i+1})$. If the second player color more than one vertex $v$ in $C$ then he can assure all of vertices $[v_i,v_{i+1})$ but $v_i$ be blue, but at the cost that all vertices a some clockwise path $[v_j,v_{j+1})$ will be red. So he wins at most $l+1$ vertices at $[v_i,v_{i+1})$ but loses at least $l+1$ vertices at $[v_j,v_{j+1})$. Thus he obtains no gain in this case too.