A good characterization has both a short proof and a short refutation (i.e., belongs to 
). Jack Edmonds is a big believer in good characterizations, and he and fellow proselytizer Václav Chvátal did a lot of preaching. For the record, I support the hype. Good characterizations give an unreasonable amount of insight into a problem.
Good characterizations often foreshadow polynomial-time solvability. Linear programming (LP) is a famous example. Long before the ellipsoid method was shown to solve LPs in polynomial time, it was known that the question — is the optimal objective of this (maximization) LP at least 
? — has both a short proof and short refutation*. Given a possible solution, one can quickly check that it satisfies the constraints and that its objective is indeed at least . For the short refutation, we have duality; simply provide a feasible solution to the dual problem that has objective less than .
The maximum clique and the vertex coloring problems have a similar sort of weak ‘duality’. That is, the clique number 
and chromatic number 
of a graph 
satisfy 
. For LPs there is strong duality; the objectives of the primal and dual LPs are equal whenever both are feasible. For clique and coloring, the ‘duality’ can be very weak. Indeed, there is a class of graphs for which the clique number is two, but the chromatic number can be arbitrarily large. Thus, we may not be able to refute the question — is the clique number at least 
? — with a proper coloring. It seems that there will never be such a good characterization for either clique or coloring (unless coNP=NP).
But what happens if we restrict ourselves to the class of graphs for which 
? In this case, we DO have a sort of strong duality. We can now quickly verify that 
when given a clique of size , and we can refute 
if given a 
-coloring. So, we have our good characterization, and you know what? For this restricted class of graphs, we CAN solve maximum clique in polynomial time! If we further restrict ourselves to the class of perfect graphs, where 
for every vertex-induced subgraph 
of , then all sorts of mathematical beauty emerge.
This leads me to the research topic generator: First look for a good characterization. If you can’t find one, artificially impose it and see what happens.
________________________________________________
*The proof that LP belongs to NP or coNP is actually more complicated than I make it seem. One needs to show that there is an optimal solution whose size (when represented in binary) is polynomial in the input size.
Farkas' Dilemma 