Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.15255 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912643871145984 |
|---|---|
| author | Balaji, Rishi Khazhinsky, Victoria Liu, Chun-Hung Qin, Kevin |
| author_facet | Balaji, Rishi Khazhinsky, Victoria Liu, Chun-Hung Qin, Kevin |
| contents | Odd coloring is a variant of proper coloring and has received wide attention. We study the list-coloring version of this notion in this paper. We prove that if $G$ is a graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, and 6 such that no 5-cycles share an edge, then for every function $L$ that assigns each vertex of $G$ a set $L(v)$ of size 5, there exists a proper coloring that assigns each vertex $v$ of $G$ an element of $L(v)$ such that for every non-isolated vertex, some color appears an odd number of times on its neighborhood. In particular, every graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, 6, and 8 is odd 5-choosable. The number of colors in these results are optimal, and there exist graphs embeddable in those surfaces of girth 6 requiring six or seven colors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_15255 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Odd list-coloring of graphs of small Euler genus with no short cycles of specific types Balaji, Rishi Khazhinsky, Victoria Liu, Chun-Hung Qin, Kevin Combinatorics Odd coloring is a variant of proper coloring and has received wide attention. We study the list-coloring version of this notion in this paper. We prove that if $G$ is a graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, and 6 such that no 5-cycles share an edge, then for every function $L$ that assigns each vertex of $G$ a set $L(v)$ of size 5, there exists a proper coloring that assigns each vertex $v$ of $G$ an element of $L(v)$ such that for every non-isolated vertex, some color appears an odd number of times on its neighborhood. In particular, every graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, 6, and 8 is odd 5-choosable. The number of colors in these results are optimal, and there exist graphs embeddable in those surfaces of girth 6 requiring six or seven colors. |
| title | Odd list-coloring of graphs of small Euler genus with no short cycles of specific types |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.15255 |