  We develop a heuristic graph coloring approximation algorithm that uses the
D-Wave 2X as an independent set sampler and evaluate its performance against a
fully classical implementation. A randomly generated set of small but hard
graph instances serves as our test set. Our performance analysis suggests
limited quantum advantage in the hybrid quantum-classical algorithm. The
quantum edge holds over multiple metrics and suggests that graph problem
applications are a good fit for quantum annealers.
