In graph theory, a class $\mathcal{G}$ is called tame if there exists a constant $c$ such that every $n$‑vertex graph $G\in\mathcal{G}$ has at most $n^c$ minimal separators. Well‑known tame families include chordal graphs, permutation graphs and circle graphs.
A key property of tame classes is that many classic optimization problems become polynomial‑time solvable on them. For instance, the Maximum Weight Independent Set problem can be solved in $\text{poly}(n)$ time for any tame class, providing a unified explanation for its tractability across diverse graph families.
The main contribution of this work is to show that List 3‑Coloring can be solved in quasipolynomial time on every tame graph class. Concretely, for an input graph with $n$ vertices, the algorithm runs in $2^{O((\log n)^k)}$ time, where $k$ is a fixed exponent depending only on the constant $c$. This demonstrates that even under the restriction that each vertex may choose from at most three colors, the list‑coloring problem remains relatively efficient on a broad spectrum of graphs.
Technical highlights
- Exploit the $n^c$ bound on minimal separators to decompose the graph into subgraphs whose structure is simple enough for recursive solving.
- Use dynamic programming during recursion to record feasible color lists for each subgraph, ensuring global consistency.
- By carefully enumerating separators and merging subgraphs, keep the recursion depth at $O(\log n)$, yielding the quasipolynomial bound.
This approach not only unifies existing polynomial‑time algorithms (e.g., list coloring on chordal graphs) but also extends to more general tame classes, offering new directions for studying the complexity of graph coloring.
Review