Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.

Ising machines have attracted attention as they are expected to solve combinatorial optimization problems at high speed with Ising models corresponding to those problems. An induced subgraph isomorphism problem is one of the decision problems, which determines whether a specific graph structure is included in a whole graph or not. The problem can be represented by equality constraints in the words of combinatorial optimization problem. By using the penalty functions corresponding to the equality constraints, we can utilize an Ising machine to the induced subgraph isomorphism problem. The induced subgraph isomorphism problem can be seen in many practical problems, for example, finding out a particular malicious circuit in a device or particular network structure of chemical bonds in a compound. However, due to the limitation of the number of spin variables in the current Ising machines, reducing the number of spin variables is a major concern. Here, we propose an efficient Ising model mapping method to solve the induced subgraph isomorphism problem by Ising machines. Our proposed method theoretically solves the induced subgraph isomorphism problem. Furthermore, the number of spin variables in the Ising model generated by our proposed method is theoretically smaller than that of the conventional method. Experimental results demonstrate that our proposed method can successfully solve the induced subgraph isomorphism problem by using the Ising-model based simulated annealing and a real Ising machine.