この修正されたインターバルグラフNP-完全の色番号を見つけるのは問題ですか？

Question

数日前私は多項式時間でこの問題（有彩色数）を解決し、その間に各頂点の色を与える貪欲なアプローチがあることを知っているので、リソース割り当ての既知の問題を解決するために間隔グラフを作成していました。グラフ（一般的なグラフの色数を求める問題は、NP-Complete（Karpによる3-充足可能性の低下））です。

私は、インターバルグラフではないが、長さ> 3の唯一のコードレスサイクルを持つグラフがある場合は、それを削除するとグラフがインターバルグラフ）は、この種のグラフNP-Completeで色数を見つける問題を引き起こしますか？

Answer 1

手の種類は、間隔グラフの色付けアルゴリズムが機能しないように単一のエッジがある場合は削除してください。区間グラフアルゴリズムを実行します。削除されたエッジの2つの端点が異なる色を持つ場合は、完了です。さもなければ、アルゴリズムを使用した色の数をCとする。 2つのエンドポイントのすべての固定カラー（Cを2つ選択）を試し、インターバルグラフアルゴリズムをもう一度試してください。それがCの色で成功すれば、あなたは完了です。それ以外の場合は、C + 1の色が必要になりますので、端点の1つを選択して一意の色を付けてください。

私はあなたがポリ時代にリムーバブルエッジを見つけることができると仮定しています。