区間グラフ
任意のグラフ G に対する、 Gの区間completionとは、部分グラフとしてGを含む同じ頂点集合上の区間グラフである。パラメータ化された区間completion(k個の追加辺をもつ区間拡大グラフを見つける)は、準指数関数時間で解決可能である。
区間グラフのパス幅は最大クリークのサイズ-1であり、彩色数-1である。任意のグラフに対するパス幅はG を部分グラフとして含む区間グラフの最小のパス幅である。。