Chip games and multipartite graph paintability

A proper coloring of a graph $G$ is a coloring $f:V(G)\rightarrow\mathbb{N}$ of the vertex set of $G$ such that no two adjacent vertices have the same color. If there exists a proper coloring of $G$ with $r$ colors, then we say that $G$ is $r$-colorable. The chromatic number of $G$ (denoted by $\chi(G)$) is the minimum number $r$ such that $G$ is $r$-colorable.

Now, consider a function $L:V(G)\rightarrow 2^{\mathbb{N}}$ (called a list-assignment) that gives each vertex $v$ its own set $L(v)\subseteq\mathbb{N}$ of possible colors. An $L$-coloring of $G$ is a proper coloring $f:V(G)\rightarrow\mathbb{N}$ such that $f(v)\in L(v)$ for each $v\in V(G)$. We say that a graph $G$ is $L$-colorable if $G$ can be properly colored with the list-assignment $L:V(G)\rightarrow\mathbb{N}.$ If $G$ is $L$-colorable for every list-assignment $L:V(G)\rightarrow 2^{\mathbb{N}}$ satisfying $|L(v)|\geq r$ for every vertex $v\in V(G)$, then we say that $G$ is $r$-choosable. The choosability of $G$, denoted by $\operatorname{ch}(G)$, is the minimum number $r$ such that $G$ is $r$-choosable.

Although the idea of choosability was established in the 1970s independently by Vizing [20] and Erdős, Rubin, and Taylor [7], it was only in 2009 that Zhu [21] and Schauz [19] independently introduced the on-line setting of list coloring. In this setting, the on-line list coloring game is played on undirected graphs, where two players, typically referred to as Lister and Painter, compete under specific rules involving the coloring of graph vertices with a set of available colors. The game consists of the following steps:

• •

  Preparation: An undirected simple graph $G$ and threshold integer $r\geq 1$ is given.

• •

  Lister Turn: On Turn $i$, Lister chooses a vertex set $S\subseteq V(G)$ consisting of currently unpainted vertices and presents the vertices in $S$ to Painter.

• •

  Painter Turn: On Turn $i$, Painter chooses an independent set $I\subseteq S$ and paints all of the vertices in $I$ with the color $i$.

• •

  Turn Alternation: The game proceeds in rounds. A round consists of Lister’s turn followed by Painter’s turn.

• •

  Win Conditions: At the end of a round, Painter wins if all of the vertices have been painted, and Lister wins if there exists an unpainted vertex that has been presented by the Lister at least $r$ times.

If the Painter has a winning strategy on $G$ with a threshold of $r,$ then $G$ is $r$-paintable. The paintability of $G$ (denoted by $\chi_{P}(G)$) is the minimum integer $r$ such that $G$ is $r$-paintable.

One may observe that for any given graph $G$, we have

To see the first inequality, note that if $G$ is $r$-choosable, then $G$ can be properly colored with the list-assignment $L$ assigning $\{1,\ldots,r\}$ to each vertex, meaning it can simply be properly colored with $r$ colors.

For the second inequality, suppose that $G$ is not $k$-choosable, so that $\operatorname{ch}(G)>k$. Then, there exists a $k$-assignment $L:V(G)\rightarrow 2^{\mathbb{N}}$ for which $G$ has no $L$-coloring. We label the colors of $\bigcup_{v\in V(G)}L(v)$ as $1,\dots,\ell$. Then, on each turn $i$, Lister reveals the color $i$ at each $v\in V(G)$ for which $i\in L(v)$. If Painter wins the game, then at the end of the game, $G$ has an $L$-coloring, a contradiction. Therefore, Painter has no winning strategy, implying $\chi_{P}(G)>k$.

In 2015, Duraj, Gutowski and Kozik [6] modified a chip game of Aslam and Dhagat [3] to be equivalent to the on-line list coloring game played on complete multipartite graphs. Before defining this chip game, we introduce the following concept: A complete k-partite graph, denoted as $K_{n_{1},\ldots,n_{k}},$ is a graph whose vertices can be partitioned into $k$ different independent sets $A_{i}$, called parts, with $|A_{i}|=n_{i}$, such that for any pair of vertices $(u,v)$ that belongs to two different parts $A_{i}$, an edge connects $u$ and $v$. When $k$ is not specified, such graphs $G$ are called complete multipartite graphs. If the $k$ parts of $G$ all have cardinality $m,$ then we write write $G=K_{m\star k}.$

Intuitively, in order to properly color a complete $k$-partite graph with as few colors as possible, each part needs to be colored with a unique color that is not used in the other parts. Thus, for every complete $k$-partite graph with $k$ nonempty parts, $\chi(G)=k$.

In the study of choosability and paintability, complete multipartite graphs have received special attention due to their connection with Ohba’s conjecture [17]. Ohba’s original conjecture from 2002 asserts that if $G$ is a graph satisfying $|V(G)|\leq 2\chi(G)+1$, then $\chi(G)=\operatorname{ch}(G)$. Later, in 2012, Huang, Wong, and Zhu [10] posed the on-line Ohba’s conjecture, which asserts that if $|V(G)|\leq 2\chi(G)$, then $\chi(G)=\chi_{P}(G)$. The stronger assumption that $|V(G)|\leq 2\chi(G)$ is necessary, as Kim, Kwon, Liu, and Zhu [13] proved that

and $K_{2\star(n-1),3\star 1}$ is a graph on $2n+1$ vertices. As a proof of either version of Ohba’s conjecture for complete multipartite graphs implies the conjecture for all graphs, complete multipartite graphs have become a special focus for research on choosability and paintability.

For certain classes of complete multipartite graphs, exact values for choosability and paintability are known. In 1993, Alon [2] proved that for each integer $n\geq 1$, $ch(K_{2\star n})=n$. Later Kim, Kwon, Liu and Zhu [13] showed that $\operatorname{ch}(K_{2\star n})=\chi_{P}(K_{2\star n})=n$. The choosability for $K_{3\star n}$ was later given by Kierstead [12], who showed that $ch(K_{3\star n})=\left\lceil\frac{4n-1}{3}\right\rceil$. Regarding the paintability of $K_{3\star n}$, Kozik, Micek and Zhu [16] found an upper bound for these graphs, implying the following:

As the choosability of a graph is always at most its paintability, it is natural then to investigate the gap between the two parameters. When Zhu [21] introduced online list coloring, he showed that $K_{6,9}$ and $K_{6,10}$ are not 3-paintable, but they are known to be 3-choosable. He then asked if the gap between the choosability and paintability of a single graph could be made arbitrarily large. Given the gap between the lower and upper bound of $\chi_{P}(K_{3\star n})$, Kozik, Micek, and Zhu [16] considered the graphs $K_{3\star n}$ as natural candidates for study, and they asked the following question:

For the question of whether the gap between a graph’s choosability and paintability can be arbitrarily large, the graph $K_{n,n}$ ended up being the key to the answer of this question. Duraj, Gutowski and Kozik [6] pointed out that a result of Radhakrishnan and Srinivasan [18] for proper hypergraph $2$-coloring implies the following upper bound:

On the other hand, letting $N$ be the smallest number such that $K_{N,N}$ is not $k$-paintable, Aslam and Dhagat [3] proved that $2^{k-1}\leq N$ and also provided a constructive strategy which demonstrated that $N\leq k\phi^{2k}$, where $\phi=\frac{\sqrt{5}+1}{2}$ is the golden ratio. Later, Duraj, Gutowski and Kozik [6] produced a strategy that improved the upper bound to $N\leq 2^{k+3}.$ As such, $N=\Theta(2^{k}),$ which implies that

This proves that $\chi_{P}(K_{n,n})-\operatorname{ch}(K_{n,n})\rightarrow\infty$ as $n\rightarrow\infty$, showing that the gap between the choosability and the paintability of a graph can be arbitrarily large.

A $(k,n_{1},\ldots,n_{m})$ chip game is equivalent to the On-line List Coloring Game played on a complete multipartite graph $K_{n_{1},\dots,n_{m}}$. In this game, two players, typically referred to as Pusher and Remover, compete under specific rules. The game is defined as follows.

We note that on each turn of a $(k,n_{1},\dots,n_{m})$ chip game, Pusher is required to move a nonempty set of chips. Furthermore, the game ends if either a single chip moves $k$ times or if all chips are removed. Therefore, the $(k,n_{1},\dots,n_{m})$ chip game ends after fewer than $k(n_{1}+\dots+n_{m})$ turns. We abbreviate the $(k,\underbrace{n,\dots,n}_{m\textrm{ times}})$ chip game as the $(k,n\star m)$ chip game.

Duraj, Gutowski, and Kozik [6] observed the following theorem for $m=2$, but their ideas naturally generalize to all positive $m$. We include a proof for completeness.

In Section 2, we compute the paintability of some complete multipartite graphs, including $K_{3\star n}$ for $n\in\{4,5,6\}$, as well as some unbalanced graphs such as $K_{2\star 4,3\star 3}$, with the help of a computer. For $K_{3\star n}$ and $n\in\{4,5,6\}$, we show that the paintabilities are $\lceil\frac{4n-1}{3}\rceil$, which agrees with their choosabilities. In Section 3, we introduce the online hypergraph pancoloring problem, which was observed by Akhmejanova, Bogdanov, and Chelnokov to be representable using a chip game. We also adapt a chip game strategy of Duraj, Gutowski, and Kozik [6] to obtain an upper bound for the minimum number of edges in a hypergraph that cannot be panchromatically $r$-colored online, improving a previous result of Khuzieva et al. [11]. Finally, in Section 4, we pose some questions.

We describe a formal framework in which our computational procedure operates. We begin with some definitions.

The value $\Gamma$ represents the row that a chip needs to reach in order for Pusher to win the chip game. We elaborate on the precise meaning of $\Gamma$ in Definition 2.6. We note that game state refers to a snapshot of the chip game, with information including the positions of all chips, the player to make the move, and the number of rows. We note further that a $(\Gamma,K\star N)$ chip game has an initial game state $(B,\Gamma,\text{Pusher})$ where $B=\{C_{1},C_{2},\cdots,C_{N}\}$ and $C_{i}=(\underbrace{(0,0),(0,0),\cdots,(0,0)}_{K\textrm{ times}})$ for each $i\in\{1,\dots,N\}$.

Note that in the definitions above, we look at the game from Pusher’s perspective, so that the term winning refers to Pusher winning, and the term losing refers to Pusher losing. Note also that both $\mathcal{W}(N,K,\Gamma)$ and $\mathcal{L}(N,K,\Gamma)$ are subsets of $\mathcal{G}_{p}(N,K,\Gamma)$, which means that only states with Pusher to move are considered as winning or losing.

For a Pusher/Remover move $\sigma$, we use $\sigma(G)$ to denote the resulting game state after applying the move. We note that according to Definition 2.7, Pusher is allowed to push chips that have already been removed from the board. This allowance does not affect the game, as a chip never returns to the board after being removed.

We use the following framework, described by Knuth and Moore [14], to assign a numerical value $F(G)$ to each game state $G\in\mathcal{G}(N,K,\Gamma)$. First, for each $G\in\mathcal{W}(N,K,\Gamma)$, we let $F(G)=1$, and for each $G\in\mathcal{L}(N,K,\Gamma)$, we let $F(G)=0$. Then, we extend $F$ to all of $\mathcal{G}(N,K,\Gamma)$ by defining $F(G)$ as follows for each $G\in\mathcal{G}(N,K,\Gamma)\setminus(\mathcal{W}(N,K,\Gamma)\cup\mathcal{L}(N,K,\Gamma))$:

where $\sigma$ runs over all legal moves of the player with the move in the position $G$. Knuth and Moore [14] show that for finite games, a function $F$ of this kind is well defined. We say that a state $G\in\mathcal{G}(N,K,\Gamma)$ is winning if $F(G)=1$, and we say that $G$ is losing if $F(G)=0$.

The following proposition follows easily from an inductive argument using the recursive definition of $F$.

We observe that by the definition of $F$, the set of game states $G\in\mathcal{G}_{p}(N,K,\Gamma)$ for which $F(G)=1$ form a winning closure, and the set of game states for which $F(G)=0$ form a losing closure. This gives us the following proposition.

In this section, we describe an algorithm that solves the following problem: given $N,K,\Gamma$, let $G_{0}=(B,\Gamma,\text{Pusher})$ be the starting game state where $B$ is a board consisting of $N$ column states, each with $K$ pairs of $(0,0)$. The board $B$ represents the starting configuration of the $(\Gamma,K\star N)$ chip game. Our goal is to check whether $G_{0}$ is a winning state (i.e. $F(G_{0})=1$). By Theorem 1.3, the paintability $\chi_{P}(K_{N\star K})$ is the smallest $\Gamma$ for which the initial state $G_{0}$ of the $(\Gamma,K\star N)$ chip game satisfies $F(G_{0})=0$. By computing $F(G_{0})$ for appropriate values of $\Gamma$, we can find the exact value of the paintability of $K_{N\star K}$ for some fixed $N$ and $K$.

The recursive definition of the function $F$ allows us to compute the value of $F(G_{0})$ by defining a tree of board states in which each leaf contains a state in which the game has ended, and then working backwards to compute the value of each intermediate game state. We use the term minimax algorithm to refer to an algorithm that computes $F(G_{0})$ using the recursive definition of $F$. However, a naive minimax algorithm needs to consider every possible game state that can be reached from the initial position and therefore is practically infeasible. Therefore, we develop several tools that help us construct a more efficient minimax algorithm that evaluates $F(G_{0})$.

By using the algorithms outlined above, we can construct a more efficient minimax algorithm to determine whether the initial state $G_{0}$ of the $(\Gamma,K\star N)$ chip game is winning or losing for Pusher. When our minimax algorithm computes $F(G_{0})$, it in fact computes a value $F(G)$ for many game states $G\in\mathcal{G}_{p}(N,K,\Gamma)$. In particular, the algorithm outputs a winning close and a losing closure, and $G_{0}$ is contained in one of these closures. By Theorem 2.13, if $G_{0}$ is in a winning (losing) closure, then it is a winning (losing) state. Therefore, in order to verify the correctness of our minimax algorithm, we can use an independent verification algorithm to verify that the winning (losing) closure containing $G_{0}$ is indeed a winning (losing) closure.

Winning closure verification: The following algorithm verifies whether a given set $\mathcal{S}\subseteq\mathcal{G}_{p}(N,K,\Gamma)$ is a winning closure. In particular, if $\mathcal{S}$ is a winning closure containing the initial game state $G_{0}$, then the following algorithm can verify that Pusher wins the $(\Gamma,K\star N)$ chip game with optimal play. The algorithm is as follows.

We input a set $\mathcal{S}\subseteq\mathcal{G}_{p}(N,K,\Gamma)$ of game states. For each $G\in\mathcal{S}$, we execute the following procedure to determine whether $G$ is good or bad:

1. (1)

   First, we check if some chip of $G$ is at or above row $\Gamma$; if so, then we say that $G$ is good.

2. (2)

   Next, we search for a Pusher move $\sigma_{p}$ such that for all Remover responses $\sigma_{r}$ to $\sigma_{p}$, $\sigma_{r}(\sigma_{p}(G))\geq G^{\prime}$ for some $G^{\prime}\in\mathcal{S}$. If such a Pusher move $\sigma_{p}$ exists, then we say $G$ is good. Otherwise, we say $G$ is bad.

If every state $S\in\mathcal{S}$ is good, then we return True. If some state $S\in\mathcal{S}$ is bad, then we return False.

Losing closure verification: The following algorithm verifies whether a given set $\mathcal{S}\subseteq\mathcal{G}_{p}(N,K,\Gamma)$ is a losing closure. In particular, if $\mathcal{S}$ is a losing closure containing the initial game state $G_{0}$, then the following algorithm can verify that Remover wins the $(\Gamma,K\star N)$ chip game with optimal play. The algorithm is as follows.

We input a set $\mathcal{S}\subseteq\mathcal{G}_{p}(N,K,\Gamma)$ of game states. For each $G\in\mathcal{S}$, we execute the following procedure to determine whether $S$ is good or bad:

1. (1)

   First, we check if some chip of $G$ is at or above row $\Gamma$; if so, then we say that $G$ is bad.

2. (2)

   Next, we check whether all chips in $G$ are removed from the board. If all chips are removed from the board, then we say that $G$ is good.

3. (3)

   For each Pusher move $\sigma_{p}$, we check whether Remover has a response move $\sigma_{r}$ such that $\sigma_{r}(\sigma_{p}(G))\leq S^{\prime}$ for some state $S^{\prime}\in\mathcal{S}$. If such a Remover move $\sigma_{r}$ exists for each Pusher move $\sigma_{p}$, then we say $G$ is good. Otherwise, we say $G$ is bad.

If every state $S\in\mathcal{S}$ is good, then we return True. If some state $S\in C$ is bad, then we return False.

We note that the verification algorithms for checking whether a set $\mathcal{S}\subseteq\mathcal{G}_{p}(N,K,\Gamma)$ is a winning or losing closure run independently of the minimax algorithm used to produce $\mathcal{S}$. The verification algorithms also have the advantage of being much simpler than the algorithm that computes the value $F(G_{0})$ for the initial state $G_{0}\in\mathcal{G}(N,K,\Gamma)$. For the reader who is interested in verifying the correctness of our computational results, we recommend checking the verification algorithms due to their simplicity.

By using our minimax algorithm to compute the value $F(G_{0})$ for the initial state $G_{0}$ of various chip games, and by verifying this value $F(G_{0})$ using our verification algorithms, we obtain the following results. The code for our algorithms is available at https://github.com/Amitten77/IML-Paintability.

We summarize the results of Theorem 2.17 in Table 1 and compare them to known lower and upper bounds of the paintabilities of the graphs considered in the theorem. The upper bounds in the table follow from Equation (2), as do the lower bounds for the paintabilities of graphs of the form $K_{3\star n}$. The other lower bounds follow from Equation (1).