Enregistré dans:
| Auteurs principaux: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2411.19462 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915039723651072 |
|---|---|
| author | Bradshaw, Peter Cao, Tianyue Chen, Atlas Dean, Braden Gan, Siyu Garcia, Ramon I. Krishnaiyer, Amit McCourt, Grace Murty, Arvind |
| author_facet | Bradshaw, Peter Cao, Tianyue Chen, Atlas Dean, Braden Gan, Siyu Garcia, Ramon I. Krishnaiyer, Amit McCourt, Grace Murty, Arvind |
| contents | 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 \geq 3$ and $n$ is large. Our method also implies a lower bound on the paintability of complete multipartite graphs with $m \geq 3$ parts of equal size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19462 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Chip games and multipartite graph paintability Bradshaw, Peter Cao, Tianyue Chen, Atlas Dean, Braden Gan, Siyu Garcia, Ramon I. Krishnaiyer, Amit McCourt, Grace Murty, Arvind Combinatorics 05C15 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 \geq 3$ and $n$ is large. Our method also implies a lower bound on the paintability of complete multipartite graphs with $m \geq 3$ parts of equal size. |
| title | Chip games and multipartite graph paintability |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2411.19462 |