Papers › Chip games and multipartite graph paintability
Chip games and multipartite graph paintability
Peter Bradshaw, Tianyue Cao, Atlas Chen, Braden Dean, Siyu Gan, Ramon I. Garcia, Amit Krishnaiyer, Grace McCourt, Arvind Murty
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We study the paintability, an on-line version of choosability, of complete multipartite graphs. We do this by considering an equivalent chip game introduced by Duraj, Gutowski, and Kozik. We consider complete multipartite graphs with $ n $ parts of size at most 3. Using a computational approach, we establish upper bounds on the paintability of such graphs for small values of $ n. $ The choosability of complete multipartite graphs is closely related to value $ p(n, m) $, the minimum number of edges in a n-uniform hypergraph with no panchromatic m-coloring. We consider an online variant of this parameter p_(OL)(n, m), introduced by Khuzieva et al. using a symmetric chip game. With this symmetric chip game, we find an improved upper bound for p_(OL)(n, m) when m ≥3 and n is large. Our method also implies a lower bound on the paintability of complete multipartite graphs with m ≥3 parts of equal size.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections