Source-linked AI summary
Graph Coloring with Color Preferences
Tomohiro Koana, Yeeseok Oh, Hirotaka Yoneda
TL;DR
The paper asks how to color graphs when vertices rank colors and proper assignments must resist profitable cyclic exchanges. It introduces stable chromatic number, proves upper and lower bounds, and studies computation, showing polynomial solvability for two colors, NP-completeness for every fixed k ≥3, and an FPT algorithm parameterized by treewidth. The stable chromatic number remains open for planar graphs.
Problem
Graph coloring with vertex preferences needs a stability requirement preventing groups from cyclically exchanging colors so that every participant strictly benefits.
Method
The paper defines stable chromatic number and combines reachability and Grundy-number bounds with complexity analysis and treewidth-parameterized algorithm design.
Results
Stable 2-colorability is polynomial-time solvable, stable k-colorability is NP-complete for every fixed k ≥3, and treewidth-based FPT algorithms find minimum stable colorings.
Takeaways & Limitations
Stable coloring is well-defined, admits structural bounds including O(t log n) colors for treewidth t, and supports exact polynomial-time minimization on trees.
Takeaways & Limitations
Determining the stable chromatic number of planar graphs remains open.
Abstract
from arXiv · showhide
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 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 $χ_\mathrm{stable}(G)$. This shows that $χ_\mathrm{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\ge 3$. Using the treewidth bound, we give a fixed-parameter tractable algorithm parameterized by treewidth.
1. Introduction
The paper introduces stable graph coloring, requiring proper assignments that resist profitable cyclic exchanges, and studies both how many colors suffice and the complexity of finding such colorings.
- Motivation: Graph coloring assigns reusable resources to pairwise-incompatible vertices, while stable coloring additionally prevents cycles in which every vertex prefers its successor’s color.Classical coloring asks only for feasibility; the preference-aware model captures agents’ strict rankings over colors.
- Motivation: In the exam-version example, students may privately exchange packets around a cycle, potentially violating properness or undermining the intended distribution.Preparing and validating many distinct versions is costly, motivating the use of as few colors as possible.
- Research questions: The paper asks how many colors suffice for stable coloring and what is the complexity of finding a stable coloring.These questions organize the paper’s bounds and algorithmic results.
- Contributions: The stable chromatic number is defined as the minimum k such that every preference profile admits a stable k-coloring.The paper bounds this invariant using reachability in acyclic orientations and the Grundy number, and determines it exactly for several elementary graph classes.
- Contributions: Stable 2-colorability is polynomial-time solvable, whereas stable k-colorability is NP-complete for every fixed k ≥3.The paper also develops fixed-parameter tractable algorithms parameterized by treewidth.
- Related work: The paper distinguishes its stability notion from Pareto optimality and from prior stable-coloring models based on Nash equilibrium or multiagent objectives.A Pareto-optimal coloring can be unstable, and a non-Pareto-optimal coloring can be stable because cyclic trades impose different constraints.
2. Preliminaries
The preliminaries define the graph, coloring, preference, and stability notation used throughout the paper, including the envy digraph characterization of blocking cycles.
- Basic notation: Graphs are finite, simple, undirected, and nonempty; V and E denote the vertex and edge sets, n = |V|, and ∆(G) the maximum degree.The notation tw(G) denotes treewidth.
- Colorings: A proper coloring is a function ϕ : V → N assigning different colors to adjacent vertices, and a k-coloring uses only colors in [k].The chromatic number χ(G) is the minimum k for which G admits a k-coloring.
- Grundy number: A Grundy coloring requires every vertex with color i to have neighbors in every lower color j < i; Γ(G) is the largest achievable number of colors.Equivalently, Γ(G) is the maximum number of colors used by First-Fit over vertex orderings.
- Preference profiles: A stable coloring instance consists of a graph and a strict total color ranking for every vertex, with only a finite prefix of each ranking needed algorithmically.For prescribed k, rankings are listed on [min{k,n}], and for minimization they are listed on [n].
- Stability: The envy graph directs uv from u toward v exactly when u prefers v’s assigned color, and a blocking cycle is a directed cycle in this graph.A coloring is stable when its envy graph has no directed cycle.
- Stability: Rotating colors along a blocking cycle preserves properness on the cycle itself, but chords or external edges can create conflicts.Thus, a blocking cycle need not correspond to a feasible simultaneous recoloring.
3. Bounds on the Stable Chromatic Number
The paper bounds the stable chromatic number using reachability, Grundy number, degree, treewidth, and graph structure, while determining exact values for several graph classes. These results include logarithmic bounds for trees and planar graphs and near-tight treewidth constructions.
- Upper bounds via reachability: χstable(G) ≤ reach(G), where reachability is minimized over acyclic orientations and counts vertices reachable from each vertex, including itself.A reverse-topological greedy coloring assigns each vertex its most preferred color unused among reachable vertices; the envy graph is then acyclic.
- Lower bounds via the Grundy number: Γ(G) ≤ χstable(G), strengthening the ordinary chromatic lower bound through a preference profile derived from a Grundy coloring.The construction forces every vertex in Grundy color class i to receive a color at least i; otherwise a two-vertex blocking cycle arises.
- Structural properties: χstable(G) is monotone under taking subgraphs, unlike the Grundy number, so subgraphs provide valid lower bounds for the stable chromatic number.Restricting a stable coloring of the supergraph preserves properness and acyclicity of the envy graph.
- Treewidth and planar graphs: Trees satisfy χstable(T) = O(log n), with some n-vertex trees requiring Ω(log n), while planar graphs satisfy χstable(G) = O(log^2 n).The treewidth constructions have bounds sr ≤ χstable(Gs,r) ≤ 2s(r − 1), whose ratio is below 2 and is asymptotically tight for trees.
4. Algorithms and Complexity
The paper establishes a complexity dichotomy for stable colorability and develops a treewidth-parameterized dynamic program that finds minimum-color stable colorings.
- Complexity dichotomy: Stable 2-colorability is solvable in polynomial time, while stable k-colorability is NP-complete for every fixed k ≥3.The polynomial-time case also constructs a stable coloring.
- Complexity dichotomy: For stable 2-colorability, nonbipartite graphs are rejected, while each bipartite component is tested under both possible proper colorings.The selected component colorings are combined after checking envy-graph acyclicity.
- Complexity dichotomy: For every fixed k ≥3, NP-hardness follows by assigning all vertices the same ranking and reducing from ordinary k-colorability.A proper k-coloring is stable because every envy arc decreases the common color order, preventing directed cycles.
- Treewidth algorithm: A width-t tree decomposition supports deciding and constructing stable k-colorings in time k^(t+1)2^O(t^2)n^O(1).The dynamic program stores bag color assignments and reachability relations while rejecting cycles.
- Treewidth algorithm: The dynamic program is correct because the root entry is true exactly when the full instance admits a stable k-coloring.Predecessor pointers reconstruct a coloring from the true table entries.
- Treewidth algorithm: A minimum-color stable coloring can be found in time 2^O(t^2)n^O(1), making stable k-colorability fixed-parameter tractable by treewidth.The algorithm tries increasing color bounds up to the treewidth-based bound; for trees, the problem is polynomial-time solvable.
5. Conclusion
The paper introduces stable graph coloring, establishes bounds for graph classes, and gives a treewidth-parameterized FPT algorithm for minimum-color stable colorings. Determining the stable chromatic number of planar graphs remains open, and other graph classes are suggested for study.
- The paper introduces stable graph coloring, where vertices have preferences over possible colors.
- The paper establishes bounds for several graph classes and gives an FPT algorithm for minimum-color stable coloring parameterized by treewidth.
- Determining the stable chromatic number of planar graphs remains open.
A. An Instance where χstable(G) > ∆+ 1
The triangular prism graph provides a preference profile with no stable 4-coloring, showing that the stable chromatic number can exceed maximum degree plus one.
- The triangular prism P is the Cartesian product C3□K2 and has matching edges between corresponding triangle vertices.Its maximum degree is 3, so proving χstable(P) ≥5 suffices for the stated separation.
- Corresponding vertices in the two triangles receive identical preferences under the constructed profile.The example specifies rankings for the corresponding vertices, including c and c′.
- Any stable coloring of one triangle using a three-color set must assign each vertex its favorite color within that set.The three favorite colors are distinct in every possible color-set row.
- The two triangles must therefore use color vectors that agree in at least one corresponding coordinate, contradicting properness across a matching edge.Thus the profile admits no stable 4-coloring, and χstable(P) ≥5.