The graph coloring problem is a well-known combinatorial problem that seeks a coloring pattern such that no two adjacent vertices share the same color. In this paper, we propose an efficient method not only for finding one solution but also for efficiently enumerating all solutions that satisfy the graph coloring constraints. Our method uses ZDDs (Zero-suppressed Binary Decision Diagrams) for efficiently indexing sets of graph coloring patterns. In addition, we propose an algorithm to generate all coloring patterns that do not split any cell of a given set partition. Our experimental results demonstrate that the proposed method significantly outperforms existing solvers. Compared to the leading ASP (Answer Set Programming) solver, our approach generates all coloring patterns more than 1,000 times faster. Our method is applicable to many practical graph instances with up to around 25 vertices, in a feasible computation time. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.

We introduce the Multi-Objective Combinatorial Reconfiguration Optimization Problem (MO-CROP), and propose an Answer Set Programming (ASP) based approach for its solution. MO-CROP involves finding the Pareto-optimal sequences (or Pareto front) of adjacent feasible solutions between two given feasible solutions of a combinatorial problem, considering both cost and length. Our algorithm is compactly implemented through multi-shot ASP solving, and its implementing solver optirecon provides an effective tool for solving MO-CROP. As a concrete example of MO-CROP, we present an ASP encoding for solving the multi-objective independent set reconfiguration optimization problem. Experimental results on the benchmark set from the recent CoRe Challenge demonstrate our approach's ability to capture diverse optimal sequences that reveal trade-offs between cost and length, a capability often lacking in traditional combinatorial reconfiguration methods. © 2025 The Authors.