|国家预印本平台
首页|Odd list-coloring of graphs of small Euler genus with no short cycles of specific types

Odd list-coloring of graphs of small Euler genus with no short cycles of specific types

Odd list-coloring of graphs of small Euler genus with no short cycles of specific types

来源:Arxiv_logoArxiv
英文摘要

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 seven colors.

Rishi Balaji、Victoria Khazhinsky、Chun-Hung Liu、Kevin Qin

数学

Rishi Balaji,Victoria Khazhinsky,Chun-Hung Liu,Kevin Qin.Odd list-coloring of graphs of small Euler genus with no short cycles of specific types[EB/OL].(2025-08-21)[2025-09-03].https://arxiv.org/abs/2508.15255.点此复制

评论