Paintability of balanced complete multipartite graphs with parts of size three: is $\chi_P(K_{3\star n})=\lceil(4n-1)/3\rceil$ for every $n$, and what is $\chi_P(K_{3\star 7})$?

The choosability of the balanced complete multipartite graphs $K_{3\star n}$ ($n$ parts of size 3) was determined by Kierstead: $ch(K_{3\star n})=\lceil(4n-1)/3\rceil$. Its on-line analogue, the paintability $\chi_P$, is only known to satisfy $\lceil(4n-1)/3\rceil\le\chi_P(K_{3\star n})\le 3n/2$ (Kozik, Micek, and Zhu). Bradshaw, Cao, Chen, Dean, Gan, Garcia, Krishnaiyer, McCourt, and Murty (2024) verified computationally, through the Duraj-Gutowski-Kozik chip game, that the two parameters coincide for $n\le 6$, and posed the two questions recorded here: determine the exact value of $\chi_P(K_{3\star 7})$, which current bounds pin down to 9 or 10, and decide whether $ch(K_{3\star n})=\chi_P(K_{3\star n})$ for every positive integer $n$. This is the part-size-three instance of the general question of how far on-line list coloring can exceed offline list coloring on complete multipartite graphs. Both questions remain open.

Background

A proper coloring of a graph assigns distinct colors to adjacent vertices, and the chromatic number $\chi(G)$ is the least number of colors that suffices. In list coloring, each vertex $v$ is given its own palette $L(v)$ of colors and one must properly color $G$ with $f(v)\in L(v)$ for every $v$; the choosability (or list chromatic number) $ch(G)$ is the least $k$ such that $G$ can be colored from every palette assignment with $|L(v)|\ge k$ at all vertices. Choosability was introduced in the 1970s by Vizing (1976) and by Erdős, Rubin, and Taylor (1979).

Schauz and Zhu (2009) introduced the adversarial, on-line version of list coloring. In the on-line list coloring game on a graph $G$ with threshold $r$, two players alternate: on each round Lister presents a set $S$ of currently unpainted vertices, and Painter colors an independent subset of $S$ with a fresh color. Painter wins if every vertex eventually gets painted; Lister wins if some vertex is presented $r$ times without being painted. If Painter has a winning strategy at threshold $r$, the graph is $r$-paintable, and the paintability $\chi_P(G)$ is the least such $r$. Reading a fixed palette assignment as a pre-scheduled Lister strategy shows $\chi(G)\le ch(G)\le\chi_P(G)$, and the choosability-paintability gap $\chi_P(G)-ch(G)$ measures how much the on-line adversary can gain.

A complete multipartite graph has its vertex set split into independent sets (parts), with every two vertices from different parts adjacent; write $K_{m\star k}$ for the balanced case of $k$ parts each of size $m$ (so $K_{3\star n}$ has $n$ parts of size 3 and $3n$ vertices, and $\chi(K_{3\star n})=n$). This convention, $m\star k$ meaning $k$ parts of size $m$, is the one used here and in the source paper. Complete multipartite graphs are the central test family for Ohba's conjecture (2002), which predicted $\chi(G)=ch(G)$ whenever $|V(G)|\le 2\chi(G)+1$, and for its on-line analogue proposed by Huang, Wong, and Zhu (2012): $\chi(G)=\chi_P(G)$ whenever $|V(G)|\le 2\chi(G)$. The bound $2\chi$ is best possible, since Kim, Kwon, Liu, and Zhu (2012) proved $\chi_P(K_{2\star(n-1),3\star 1})=n+1>n=\chi(K_{2\star(n-1),3\star 1})$, a graph on $2n+1$ vertices.

For parts of size 2 the parameters are completely understood: Alon (1993) proved $ch(K_{2\star n})=n$, and Kim, Kwon, Liu, and Zhu proved $\chi_P(K_{2\star n})=n$ as well. For parts of size 3, Kierstead (2000) proved $ch(K_{3\star n})=\lceil(4n-1)/3\rceil$, but on the on-line side only the bounds $\lceil(4n-1)/3\rceil\le\chi_P(K_{3\star n})\le 3n/2$ are known, the upper bound being due to Kozik, Micek, and Zhu (2014). The gap question matters beyond this family: Zhu asked whether $ch$ and $\chi_P$ of a single graph can differ by an arbitrarily large amount, and the answer is yes, witnessed already in the bipartite case, where $ch(K_{n,n})=\log_2 n-\Omega(\log_2\log_2 n)$ (via a hypergraph 2-coloring theorem of Radhakrishnan and Srinivasan) while $\chi_P(K_{n,n})=\log_2 n+O(1)$ (Aslam and Dhagat 1993; Duraj, Gutowski, and Kozik 2016). Kozik, Micek, and Zhu therefore proposed $K_{3\star n}$ as the natural next family and asked whether $\chi_P(K_{3\star n})-ch(K_{3\star n})$ is unbounded.

The key technical tool is the chip game of Duraj, Gutowski, and Kozik, equivalent to the on-line list coloring game on complete multipartite graphs. In the $(k,n_1,\dots,n_m)$ chip game, a board has $m$ columns with rows labeled $0$ to $k$, and column $i$ starts with $n_i$ chips in row 0. Each round, Pusher (modeling Lister) pushes a nonempty set of chips one row upward, then Remover (modeling Painter) picks one column and removes from it exactly the chips that were just pushed. Pusher wins if some chip reaches row $k$; Remover wins if all chips are removed first. The equivalence (recorded as Theorem 1.3 of the source paper) states that $\chi_P(K_{n_1,\dots,n_m})>k$ if and only if Pusher has a winning strategy in the $(k,n_1,\dots,n_m)$ chip game.

Using this equivalence with a pruned minimax search whose output certificates (winning and losing closures of game states) are independently verified, Bradshaw, Cao, Chen, Dean, Gan, Garcia, Krishnaiyer, McCourt, and Murty (2024) determined the exact paintabilities $\chi_P(K_{3\star 4})=5$, $\chi_P(K_{3\star 5})=7$, and $\chi_P(K_{3\star 6})=8$, together with several unbalanced graphs with parts of size 2 and 3. In every computed case with parts of size 3 the paintability equals the choosability $\lceil(4n-1)/3\rceil$, so the choosability-paintability gap is zero for all $n\le 6$. Their computation stalled at $n=7$, and they posed the questions that form this problem.

Problem Statement

Throughout, $K_{3\star n}$ is the balanced complete multipartite graph with $n$ parts of size 3 ($3n$ vertices, $\chi=n$): its vertex set splits into $n$ independent sets of size 3, and every two vertices from different parts are adjacent. The choosability $ch(G)$ is the least $k$ such that $G$ admits a proper coloring from every palette assignment with $|L(v)|\ge k$ at every vertex, and the paintability $\chi_P(G)$ is the least $r$ such that Painter wins the on-line list coloring game on $G$ with threshold $r$: in each round of that game Lister presents a set of currently unpainted vertices and Painter colors an independent subset of them with one fresh color; Painter wins if every vertex is eventually painted, and Lister wins if some vertex is presented $r$ times without being painted. Always $\chi(G)\le ch(G)\le\chi_P(G)$.

Determine the paintability of the family $\{K_{3\star n}\}_{n\ge 1}$, in particular decide whether on-line list coloring is ever strictly harder than offline list coloring on this family. Concretely, answer the two linked questions posed as Questions 4.1 and 4.2 of Bradshaw et al. (2024):

1. What is the exact value of $\chi_P(K_{3\star 7})$? The known bounds are $9=ch(K_{3\star 7})=\lceil(4\cdot 7-1)/3\rceil\le\chi_P(K_{3\star 7})\le\lfloor 3\cdot 7/2\rfloor=10$, so the answer is 9 or 10.

2. Is $ch(K_{3\star n})=\chi_P(K_{3\star n})$, that is, $\chi_P(K_{3\star n})=\lceil(4n-1)/3\rceil$, for every positive integer $n$?

These are one objective at two granularities: a positive answer to question 2 implies $\chi_P(K_{3\star 7})=9$, while a negative answer to question 2 requires an explicit $n$ together with a winning strategy for Lister in the on-line list coloring game on $K_{3\star n}$ at threshold $k=\lceil(4n-1)/3\rceil$, certifying $\chi_P(K_{3\star n})\ge\lceil(4n-1)/3\rceil+1$. By the chip-game equivalence (Theorem 1.3 of the source paper), such a certificate is equivalently a winning Pusher strategy in the $(k,3\star n)$ chip game: a board of $n$ columns of 3 chips with rows labeled $0$ to $k$, where each round Pusher pushes a nonempty set of chips one row upward and Remover removes exactly the just-pushed chips of one column, and Pusher wins if some chip reaches row $k$. Equality has been verified for $1\le n\le 6$. Question 2 is settled by either a proof of equality for all $n\ge 1$ or such an explicit counterexample, and the value of $\chi_P(K_{3\star 7})$ remains an independent question in either case (a counterexample at a single $n\ne 7$ settles question 2 but does not settle question 1).

References

1. Peter Bradshaw, Tianyue Cao, Atlas Chen, Braden Dean, Siyu Gan, Ramon I. Garcia, Amit Krishnaiyer, Grace McCourt, Arvind Murty, "Chip games and multipartite graph paintability" (2024), arXiv:2411.19462, DOI 10.48550/arxiv.2411.19462, https://arxiv.org/abs/2411.19462
2. Jakub Kozik, Piotr Micek, Xuding Zhu, "Towards an on-line version of Ohba's conjecture", European Journal of Combinatorics 36 (2014) 110-121, DOI 10.1016/j.ejc.2013.07.003, https://doi.org/10.1016/j.ejc.2013.07.003
3. Henry A. Kierstead, "On the choosability of complete multipartite graphs with part size three", Discrete Mathematics 211(1-3) (2000) 255-259, DOI 10.1016/S0012-365X(99)00157-0, https://doi.org/10.1016/S0012-365X(99)00157-0
4. Seog-Jin Kim, Young Soo Kwon, Daphne Der-Fen Liu, Xuding Zhu, "On-line list colouring of complete multipartite graphs", Electronic Journal of Combinatorics 19(1) (2012) Paper 41, DOI 10.37236/2050, https://doi.org/10.37236/2050
5. Lech Duraj, Grzegorz Gutowski, Jakub Kozik, "Chip games and paintability", Electronic Journal of Combinatorics 23(3) (2016) Paper P3.3, DOI 10.37236/5723, arXiv:1506.01148, https://doi.org/10.37236/5723
6. Po-Yi Huang, Tsai-Lien Wong, Xuding Zhu, "Application of polynomial method to on-line list colouring of graphs", European Journal of Combinatorics 33(5) (2012) 872-883, DOI 10.1016/j.ejc.2011.09.020, https://doi.org/10.1016/j.ejc.2011.09.020
7. Xuding Zhu, "On-line list colouring of graphs", Electronic Journal of Combinatorics 16(1) (2009) R127, DOI 10.37236/216, https://doi.org/10.37236/216
8. Uwe Schauz, "Mr. Paint and Mrs. Correct", Electronic Journal of Combinatorics 16(1) (2009) R77, DOI 10.37236/166, https://doi.org/10.37236/166
9. Kyoji Ohba, "On chromatic-choosable graphs", Journal of Graph Theory 40(2) (2002) 130-135, DOI 10.1002/jgt.10033, https://doi.org/10.1002/jgt.10033
10. Paul Erdős, Arthur L. Rubin, Herbert Taylor, "Choosability in graphs", Congressus Numerantium 26 (1979) 125-157, zbMATH 0469.05032, https://zbmath.org/3735847
11. Noga Alon, "Restricted colorings of graphs", in Surveys in Combinatorics 1993, London Mathematical Society Lecture Note Series 187, Cambridge University Press (1993) 1-33, DOI 10.1017/cbo9780511662089.002, https://doi.org/10.1017/cbo9780511662089.002
12. Javed A. Aslam, Aditi Dhagat, "On-line algorithms for 2-coloring hypergraphs via chip games", Theoretical Computer Science 112(2) (1993) 355-369, DOI 10.1016/0304-3975(93)90025-O, https://doi.org/10.1016/0304-3975(93)90025-O
13. Jaikumar Radhakrishnan, Aravind Srinivasan, "Improved bounds and algorithms for hypergraph 2-coloring", Random Structures and Algorithms 16(1) (2000) 4-32, DOI 10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2, https://doi.org/10.1002/(SICI)1098-2418(200001)16:1%3C4::AID-RSA2%3E3.0.CO;2-2
14. Alina E. Khuzieva, Dmitry A. Shabanov, Polina O. Svyatokum, "On-line and list on-line colorings of graphs and hypergraphs", Moscow Journal of Combinatorics and Number Theory 7(4) (2017) 39-57, zbMATH identifier 7321503, https://zbmath.org/7321503 (no Crossref DOI; journal archive at mjcnt.phystech.edu)
15. Danila Cherkashin, "A note on panchromatic colorings", Discrete Mathematics 341(3) (2018) 652-657, DOI 10.1016/j.disc.2017.10.030, https://doi.org/10.1016/j.disc.2017.10.030