  Quantum devices can be used to solve constrained combinatorial optimization
(COPT) problems thanks to the use of penalization methods to embed the COPT
problem's constraints in its objective to obtain a quadratic unconstrained
binary optimization (QUBO) reformulation of the COPT. However, the particular
way in which this penalization is carried out, affects the value of the penalty
parameters, as well as the number of additional binary variables that are
needed to obtain the desired QUBO reformulation. In turn, these factors
substantially affect the ability of quantum computers to efficiently solve
these constrained COPT problems. This efficiency is key towards the goal of
using quantum computers to solve constrained COPT problems more efficiently
than with classical computers. Along these lines, we consider an important
constrained COPT problem; namely, the maximum $k$-colorable subgraph (M$k$CS)
problem, in which the aim is to find an induced $k$-colorable subgraph with
maximum cardinality in a given graph. This problem arises in channel assignment
in spectrum sharing networks, VLSI design, human genetic research, and
cybersecurity. We derive two QUBO reformulations for the M$k$CS problem, and
fully characterize the range of the penalty parameters that can be used in the
QUBO reformulations. Further, one of the QUBO reformulations of the M$k$CS
problem is obtained without the need to introduce additional binary variables.
To illustrate the benefits of obtaining and characterizing these QUBO
reformulations, we benchmark different QUBO reformulations of the M$k$CS
problem by performing numerical tests on D-Wave's quantum annealing devices.
These tests also illustrate the numerical power gained by using the latest
D-Wave's quantum annealing device.
