Is there a problem more difficult than NP-complete in graph theory?

Question

There are some decision problems being NP-complete in graph theory, including the problem of deciding if a graph has a hamilton cycle, or determing the chromatic number. Since the number of labeled graphs is $2^\frac{n(n-1)}{2}$, I think that there are no problems in graph theory more difficult than NP-complete.

• Is this conjecture true ?
• If not, are there even undecidable problems in graph theory ?

Answer 1

You might be interested in the answers to this related mathoverflow question, which gives several undecidable graph-theoretic problems. (Of course, it's somewhat a matter of taste whether a given problem is really "graph-theoretic" or not.)

Answer 2

Are you familiar with #P-complete problems? The prototypical example is:

HC#: Given a graph $G$, how many Hamiltonian cycles does it have?

Clearly, an efficient solution to HC# would immediately solve the NP-complete Hamiltonian Cycle (HC) problem, and by extension all NP-complete problems. On the other hand, it's not clear at all that an efficient solution to HC would be any help at all in solving HC#.

There are counting versions of almost any NP-complete problem you can think of: Given a graph $G$, how many 3-colorings does it have? Given a graph $G$, and a positive integer $n$, how many vertex covers of size $n$ does $G$ have? Each is evidently at least as hard, and probably much harder, than the corresponding NP-complete decision problem.