Graph problems with good characterization but not known to be in $P$

Question

A decision problem has good characterization if it is in $NP \cap coNP$. Many natural graph problems have good characterizations. For instance, Kuratuwski's Theorem gives good characterization of planar graphs. Konig's Theorem gives good characterization of bipartite graphs. Tutte's Theorem gives good characterization of graphs that have perfect matching. Euler's Theorem gives good characterization of Eulerian graphs. All these recognition problems have polynomial-time algorithms.

Is there a natural graph problem that has good characterization but not known to be in $P$? A pointer to a survey of such problems would be appreciated.

Answer 1

In one of my blog posts, I mentioned four problems (Factoring, Parity Games, Stochastic Games, A Lattice Problem) that are known to be in $NP \cap coNP$ but not known to be in $P$.

Parity Games and Stochastic Games can be considered as "graph problems".

Also, The Two Bicliques Problem is in $NP \cap coNP$. This is a natural graph problem that is not known to be in $P$.

Answer 2

Determining the winner of a "parity game" is known to be in $NP\cap coNP$, but it is an outstanding open problem whether it is in $P$. See e.g.,

http://lovelace.thi.informatik.uni-frankfurt.de/~klauck/XOR.pdf

Note, however, that a parity game is defined by an annotated directed graph, so you might not want to consider it a "natural graph problem."

Answer 3

Kuperberg recently proved that knottedness (of a given knot diagram) is in NP ∩ coNP, assuming that the generalized Riemann hypothesis is true. A knot diagram is close enough to a graph that I think this counts as an answer to your question.