NP完全問題
グラフ G {\displaystyle G} と3以上の上界 k {\displaystyle k} が与えられる。このとき、 G {\displaystyle G} はk-点彩色を持つか?という問題。 k = 2 {\displaystyle k=2} のときはこれはグラフが二部グラフかどうか決定する問題と同じになる。
有向グラフ G {\displaystyle G} が与えられる。このとき G {\displaystyle G} にハミルトン閉路が存在するか?という問題。この問題の最適化版(できるだけ最大次数が小さな全点木を求める)は、最小次数全点木問題と呼ばれる。