公平な色彩

数学の一分野であるグラフ理論において、公平な彩色とは、無向グラフの頂点に色を割り当てることである。

• 隣接する頂点は同じ色ではなく、
• 任意の 2 つのカラー クラスの頂点の数は、最大で 1 つ異なります。

つまり、頂点を異なる色に分割することが可能な限り均一である。例えば、各頂点に異なる色を与えることは公平ではあるが、通常、最適な公平な彩色に必要な色よりもはるかに多くの色を使用することになる。公平な彩色を定義する同等の方法は、与えられたグラフを、同じ頂点セットを持つトゥラングラフのサブグラフとして埋め込むことである。公平な彩色に関連付けられた彩色数は 2 種類ある。^[1]グラフGの公平な彩色数は、 Gがk色で公平な彩色を持つ最小の数kである。しかし、G はより多くの色数に対しては公平な彩色を持たない可能性がある。Gの公平な彩色閾値は、G がk以上の任意の数の色に対して公平な彩色を持つ最小の k である。[ 2 ^]

ポール・エルデシュ (1964)によって予想として提起され、アンドラーシュ・ハイナルとエンドレ・セメレディ(1970) によって証明されたハイナル・セメレディの 定理は、最大次数 Δ を持つ任意のグラフは Δ + 1 色で公平に彩色されることを述べています。関連するいくつかの予想は未解決のままです。多項式時間アルゴリズムは、この境界に一致する彩色を見つけることも、^[3]特別なクラスのグラフの最適彩色を見つけることも知られていますが、任意のグラフが与えられた色数で公平に彩色されるかどうかを判断するより一般的な問題はNP完全です。

星K _{1,5 は}、 中心の頂点が 1 つだけあり、他の 5 つの頂点とつながっている完全な二部グラフなので、2 色で色付けできます。ただし、結果として得られる色付けでは、1 つの頂点が 1 つの色クラスに属し、5 つの頂点が別の色クラスに属するため、公平ではありません。このグラフの公平な色付けにおける最小の色数は 4 です。中心の頂点はその色クラスに属する唯一の頂点でなければならないため、他の 5 つの頂点は少なくとも 3 つの色クラスに分割して、他の色クラスがすべて最大で 2 つの頂点を持つようにする必要があります。

より一般的には、マイヤー (1973) は、任意の星K _{1, n は}任意の公平な彩色で色を必要とすることを観察しています。したがって、グラフの彩色数は、その公平な彩色数とn /4 ほどの係数で異なる場合があります。K 1,5 の最大次数は 5 であるため、_Hajnal -Szemerédi の定理によって保証される色の数は 6 であり、各頂点に異なる色を割り当てることで実現されます。 ${\displaystyle \scriptstyle 1+\lceil n/2\rceil }$

別の興味深い現象は、別の完全二部グラフK _{2 n  + 1,2 n  + 1で示されます。このグラフは、二分割によって与えられた公平な 2 色付けを持ちます。しかし、公平な (2} n + 1)色付けは持ちません 。頂点をこれだけ多くの色クラスに公平に分割するには、クラスごとにちょうど 2 つの頂点が必要ですが、二分割の両側は頂点の数が奇数であるため、それぞれペアに分割できません。したがって、このグラフの公平な彩色閾値は 2 n  + 2 であり、公平な彩色数 2 よりも大幅に大きくなります。

ブルックスの定理は、最大次数 Δ を持つ連結グラフはすべて Δ 彩色を持つが、2 つの例外 (完全グラフと奇数サイクル) があることを述べています。ただし、この彩色は一般に公平とはほど遠い可能性があります。ポール・エルデシュ (1964)は、もう 1 色追加するだけで公平な彩色が可能になると予想しました。つまり、最大次数 Δ を持つグラフはすべて、Δ + 1 色で公平な彩色を持つということです。Δ = 2 の場合は単純で (パスとサイクルの任意の和集合は、サイクルを閉じるときに繰り返しをわずかに調整して、3 色の繰り返しパターンを使用して公平に彩色できます)、Δ + 1=  n /3 の場合は、以前に Corrádi & Hajnal (1963) によって解決されていました。完全な予想は Hajnal & Szemerédi (1970) によって証明され、現在では Hajnal–Szemerédi 定理として知られています。より簡単な証明は Kierstead & Kostochka (2008) によって与えられました。これほど多くの色で公平な彩色を見つける多項式時間アルゴリズムは Kierstead と Kostochka によって説明されました。彼らは、Marcelo Mydlarz と Endre Szemerédi が以前に未発表の多項式時間アルゴリズムを考案したとしています。Kierstead と Kostochka はまた、定理を強化して、隣接する 2 つの頂点の次数が最大で 2 k + 1 になる場合は常に公平なk+1彩色が存在することを示すことも発表しましたが、証明はしてい ません。

マイヤー (1973) は、公平な彩色に関するブルックスの定理の一種を予想した。最大次数 Δ の連結グラフはすべて、完全グラフと奇数サイクルを除いて、Δ 色以下の公平な彩色を持つというものである。この予想を強化したバージョンでは、そのようなグラフはすべて、ちょうど Δ 色の公平な彩色を持つが、2 分割の両側に同じ奇数の頂点がある完全 2 部グラフという例外が追加される、としている。 ^[1]

Seymour (1974) は、稠密なグラフはハミルトンであるというディラックの定理も包含する Hajnal–Szemerédi の定理の強化を提案しました。彼は、n頂点グラフのすべての頂点に少なくともkn /( k + 1) 個の隣接頂点がある場合、そのグラフには、 nサイクルで最大kステップ離れた 頂点を接続して形成されるグラフがサブグラフとして含まれると予想しました。k = 1の場合は ディラックの定理そのものです。Hajnal–Szemerédi の定理は、この予想から、より大きな値の k に対する予想を特定のグラフの補グラフに適用し、 n サイクルからの頂点の連続する部分列をカラー クラスとして使用することで復元できます。Seymourの予想は、すべての頂点に少なくともkn /( k  + 1)+o( n ) 個の隣接頂点があるグラフに対して、近似的に証明されています。 ^[4]証明には、ハイナル・セメレディ定理そのものを含むいくつかの深いツールが使用されています。

Hajnal–Szemerédi 定理のさらに別の一般化は、Bollobás–Eldridge–Catlin 予想（または略して BEC 予想）です。^[5]これは、G ₁とG _{2 がそれぞれ最大次数 Δ 1}と Δ _{2 を持つ}n頂点上のグラフであり、 (Δ ₁  + 1)(Δ ₂  + 1) ≤  n+1である場合、G ₁とG _{2 は}パック可能であることを述べています。つまり、G ₁とG _{2 は、}共通の辺を持たないn頂点の同じセット上に表すことができます。 Hajnal–Szemerédi 定理は、 G _{2 が}クリークの互いに素な和である場合のこの予想の特殊なケースです。 Catlin (1974) は、 Δ ₁と Δ ₂に対して、そのようなパックが存在することが保証される、類似しているがより強い条件を示しています。

最大次数Δを持つ任意の木について、均等な彩色数は最大で

${\displaystyle 1+\lceil \Delta /2\rceil }$^[6]

最悪のケースは星の場合に発生します。しかし、ほとんどの木は公平な彩色数がかなり小さくなります。n頂点の木がΔ ≤ n /3 − O(1)を持つ場合、 3 色のみで公平な彩色になります。^{[7] Furmańczyk (2006)は}グラフ積の公平な彩色数を研究しています。

できるだけ少ない色数（Hajnal-Szemerédi 境界以下）で公平な彩色を見つける問題も研究されている。グラフ彩色から公平な彩色への直接的な還元は、グラフに十分な数の孤立した頂点を追加することによって証明でき、グラフが与えられた数の色数（2 以上）で公平な彩色を持つかどうかをテストすることがNP 完全であることを示す。しかし、この問題は、グラフの特別なクラスに制限した場合、またはパラメータ化された複雑さの観点から見ると、より興味深いものになる。Bodlaender と Fomin (2005) は、グラフGと色の数cが与えられた場合、 G が公平なc彩色を許容するかどうかを O( n ^{O( t )} )時間でテストできることを示した。ここで、 tはGのツリー幅である。特に、公平な彩色は、ツリー（Chen と Lih 1994 により以前に知られていた）および外平面グラフに対して多項式時間で最適に解くことができる。分割グラフの公平な彩色には多項式時間アルゴリズムも知られている。^[8]しかし、Fellowsら(2007)は、木幅がアルゴリズムのパラメータである場合、問題はW[1]困難であることを証明している。したがって、このパラメータに依存しない多項式時間アルゴリズムが存在する可能性は低く、パラメータへの依存性が実行時間の式の指数から外れる可能性さえ低い。

Meyer (1973) が提案した公平な彩色の動機の 1 つは、スケジュールの問題に関するものです。このアプリケーションでは、グラフの頂点は実行されるタスクのコレクションを表し、エッジは同時に実行されるべきではない 2 つのタスクを接続します。このグラフの彩色は、タスクを同時に実行できるサブセットに分割することを表します。したがって、彩色の色の数は、タスク全体を実行するために必要な時間ステップの数に対応します。負荷分散を考慮すると、各時間ステップで同じまたはほぼ等しい数のタスクを実行することが望ましく、この分散はまさに公平な彩色によって達成されます。Furmańczyk (2006) は、このタイプのスケジュール問題の具体的なアプリケーションとして、利用可能な時間スロットにコースを均等に分散し、互換性のないコースのペアが同時にスケジュールされることを回避する方法で、大学のコースを時間スロットに割り当てることを述べています。

Hajnal-Szemerédi の定理は、依存性が限定されたランダム変数の合計の分散を制限するためにも使用されています (Pemmaraju 2001; Janson & Ruciński 2002)。( Lovász の局所補題の設定のように) 各変数が最大 Δ 個の他の変数に依存している場合、依存グラフの公平な色付けを使用して変数を独立したサブセットに分割し、その中でChernoff 境界を計算できます。その結果、分割が公平でない方法で実行された場合よりも、分散の全体的な境界が狭くなります。

• ECOPT 公平な色付け問題を解決するための分岐カットアルゴリズム