I enjoyed your post but I have a disagreement. Graph Coloring is np-complete or np-hard depending on what question you're asking. Grover's algorithm for unstructured search only provides a quadratic boost. If you're pulling from the papers on adiabatic evolution, these are simulated small instances with acceptance probabilities that would likely not be economical in real world scenarios.

For quantum computers to solve np-complete problems in polynomial time would be highly surprising and seems just too good of an outcome. Especially considering the work showing exponential slowdowns for simple problems that defeat local search algorithms like QA.

That said, there'll likely be many practical problems for which quantum annealing provides speed ups which vastly outstrip classical computers.