{"id":"arxiv/2609.00569","url":"https://arxiv.org/abs/2609.00569","tags":["cs.GT","math.CO"],"score":0,"title":"Graph Coloring with Color Preferences","domain":"cs.GT","source":"arxiv","authors":["Tomohiro Koana","Yeeseok Oh","Hirotaka Yoneda"],"reviews":0,"subject":"cs.GT","summary":"We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its original one. We define the stable chromatic number $χ_\\mathrm{stable}(G)$ of a graph $G$ as the minimum integer $k$ such that every preference profile admits a stable $k$-coloring of $G$. We establish several upper and lower bounds. In particular, for any acyclic orientation of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-01","reactions":{}}