I wonder whether there is a website or a survey collecting all known NP-complete or NP-hard problems on graph theory?
NP-Complete Problems in Graph Theory – Comprehensive Survey
algorithmsgraph theorynp
Related Solutions
A complete graph invariant is computationally equivalent to a canonical labeling of a graph. A canonical labeling is by definition an enumeration of the vertices of every finite graph, with the property that if two graphs are isomorphic as unlabeled graphs, then they are still isomorphic as labeled graphs. If you have a black box that gives you a canonical labeling, then obviously that is a complete graph invariant. On the other hand, if you have a complete graph invariant for unlabeled graphs, then you also have one for partially labeled graphs. So given a black box that computes a complete graph invariant, you can assign the label 1 to the vertex that minimizes the invariant, then assign a label 2 to a second vertex than again minimizes the invariant, and so on.
There are algorithms to decide graph isomorphism for certain types of graphs, or for all graphs but with varying performance, and there are algorithms for canonical labeling, again with varying performance. It is understood that graph isomorphism reduces to canonical labeling, but not necessarily vice versa. The distinction between the two problems is discussed in this classic paper by Babai and Luks.
One natural canonical labeling of a graph is the one that is lexicographically first. I think I saw, although I don't remember where, a result that computing this canonical labeling for one of the reasonable lex orderings on labeled graphs is NP-hard. But there could well be a canonical labeling computable in P that doesn't look anything like first lex.
As Douglas says, nauty is a graph computation package that includes a canonical labeling function. It is often very fast, but not always. Nauty uses a fancy contagious coloring algorithm. For a long time people thought that contagious coloring algorithms might in principle settle the canonical labeling and graph isomorphism problems, but eventually counterexamples were found in another classic paper by Cai, Furer, and Immerman. It was not clear at first whether this negative result would apply to nauty, but it seems that it does.
This 2003 paper shows there has been quite a bit of work. The focus is on "fast" exponential-time solutions to NP-hard problems, including the TSP, SAT, knapsack problems, graph coloring, to mention a few:
Woeginger, Gerhard J. "Exact algorithms for NP-hard problems: A survey." Combinatorial Optimization—Eureka, You Shrink!. Springer Berlin Heidelberg, 2003. 185-207. PDF download
For example, there is an exact algorithm for the Euclidean TSP in the plane (ETSP) with time complexity $O(2^{\sqrt{n} \log n})$. But as is well-known, S. Arora and J.S.B. Mitchell found PTAS's to solve ETSP.
This paper has been cited over 500 times since, showing there has been significant subsequent work.
Best Answer
Here is a section on graph theory in A compendium of NP optimization problems by P. Crescenzi and V. Kann.