2部グラフの最適なエッジカラーリング

Question

私は以下の問題に直面しました：2部グラフで最適なエッジカラーリングを見つけました。私は欲張りの色付けアルゴリズムが時には最適な色数を返せないことがあることを知っています。 「貪欲な色付けアルゴリズム」とは、最高次数を持つ最初の頂点を選択し、1 ...度の色でその辺の色をつけた後、度数が< =の頂点を選択して、利用可能な番号（隣人が使用していない最小の番号）、次の頂点を選択するなど

しかし、私は1つの修正を導入しました：最初に選ばれた頂点Iの色が降順1）、および1つ前のように次の頂点の辺があります。この変更により、私は最高の色数を得ました。しかし、私はそれが常にルールであるとはかなり確信していません。エッジカラーリングアルゴリズムのこのバージョンが最適かどうか、誰かがどのような反例を示すことができるかを誰かが知っていますか？

Answer 1

「純粋な」グリーディアルゴリズムの反例を取り、「洗練された」グリーディアルゴリズムの反例にすることができます。適切な程度のダミーノードを挿入するだけで、後方の着色を「吸収する」。グラフの任意の部分に度nの新しいノードを作成することができます。nの新しいノードを他の部分に挿入して、単一のエッジで目的の新しいノードに接続します。

降順で色付けされたすべてのノードが新しく挿入されるため、元の反例のすべてのノードは昇順で色付けされるため、元の「素朴な」グリーディアルゴリズムと同じ色が得られます。最適なカラーリングは、元のグラフの次数と少なくとも同じ色を持ち、新しく挿入されたノードはすべて元のグラフの最大次数よりも小さいので、新しいグラフはオリジナルよりも多くの色を必要としません。したがって、元のグラフに必要な色よりも多くの色を持つ「洗練された」アルゴリズムによって生成された色付けは、新しいグラフには最適ではありません。

たとえば、ノードB、C、Dが左側にあり、E、F、G、Hが右側にあるグラフを考えます。それは次のエッジを持っています：

B connects to E, F, and G 
C connects to E, F, and G 
D connects to G and H 

ここでは、タッチする最初のノードだけが降順で色付けされると仮定します。 （他のノードについては、「降順」が何を意味するのかは明らかではない - 最大値から下降する）ノードの次数が十分に高くない可能性がある。

したがって、右に3つのノードI、J、Kがあります。接続は、洗練された貪欲アルゴリズムは、したがって色AI-3、AJ-2、AK-1は、その後、残りのノード上のナイーブ貪欲アルゴリズムとして進行する今

A connects to I, J, and K 
B connects to E, F, and G 
C connects to E, F, and G 
D connects to G and H 

あります。