  Current quantum computing devices have different strengths and weaknesses
depending on their architectures. This means that flexible approaches to
circuit design are necessary. We address this task by introducing a novel
space-efficient quantum optimization algorithm for the graph coloring problem.
Our circuits are deeper than the ones of the standard approach. However, the
number of required qubits is exponentially reduced in the number of colors. We
present extensive numerical simulations demonstrating the performance of our
approach. Furthermore, to explore currently available alternatives, we perform
a study of random graph coloring on a quantum annealer to test the limiting
factors of that approach, too.
