Graph Coloring with Color Preferences
Abstract
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 χ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 the edges of G, the largest number of vertices reachable from a vertex by directed paths, including the vertex itself, is an upper bound on χstable(G). This shows that χstable(G) is well-defined. We also show that O(t log (1+n/t)) colors suffice for an n-vertex graph G of treewidth t, and complement this with a lower bound in terms of the Grundy number. Turning to the problem of finding a minimum stable coloring for a given profile, we show that stable $2$-colorability is polynomial-time solvable, whereas stable k-colorability is NP-complete for every fixed k≥ 3. Using the treewidth bound, we give a fixed-parameter tractable algorithm parameterized by treewidth.
Related
- Edge‐Coloring a Graph G so That Every Copy of a Graph H Has an Odd Color Class
- Affine G-multibiquandle modules for colored links I: representability of coloring functors and color-profile polynomials
- Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
- Dynamic Coloring and Graph Squares of Regular Graphs
- Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
BibTeX
@misc{koana2026graph,
title = {{Graph Coloring with Color Preferences}},
author = {Tomohiro Koana and Yeeseok Oh and Hirotaka Yoneda},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00569},
eprint = {2609.00569},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00569},
}
RIS
TY - UNPB
TI - Graph Coloring with Color Preferences
AU - Tomohiro Koana
AU - Yeeseok Oh
AU - Hirotaka Yoneda
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00569
UR - https://arxiv.org/abs/2609.00569
AB - 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 χ_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 the edges of G, the largest number of vertices reachable from a vertex by directed paths, including the vertex itself, is an upper bound on χ_stable(G). This shows that χ_stable(G) is well-defined. We also show that O(t log (1+n/t)) colors suffice for an n-vertex graph G of treewidth t, and complement this with a lower bound in terms of the Grundy number. Turning to the problem of finding a minimum stable coloring for a given profile, we show that stable $2$-colorability is polynomial-time solvable, whereas stable k-colorability is NP-complete for every fixed k≥ 3. Using the treewidth bound, we give a fixed-parameter tractable algorithm parameterized by treewidth.
ER -