リストの色分け

数学の一分野であるグラフ理論において、リスト彩色は各頂点を許容色のリストに制限できるグラフ彩色の一種である。これは1970年代にVizing とErdős、Rubin、Taylorによる独立した論文で初めて研究された。^[1]

グラフGと、各頂点vに対する色の集合L ( v ) (リストと呼ばれる) が与えられた場合、リスト彩色は、すべての頂点vをリストL ( v )の色にマッピングする選択関数です。グラフ彩色と同様に、リスト彩色は一般に適切である、つまり、隣接する 2 つの頂点が同じ色を受け取ることはないと想定されます。各頂点にk色のリストを割り当てる方法に関係なく、適切なリスト彩色を持つ場合、グラフはk選択可能(またはkリスト彩色可能) です。グラフGの選択可能性(またはリスト彩色可能、リスト彩色数) ch( G )は、 Gがk選択可能である最小の数kです。

より一般的には、各頂点vに正の整数f ( v )を割り当てる関数fについて、各頂点vにf ( v )色のリストを割り当てる方法に関係なく、グラフG がリスト色付けを持つ場合、 f選択可能（またはfリスト色可能）です。特に、すべての頂点 v に対して f ( v ) = k の場合、 f選択可能性はk選択可能性に対応します。

完全な二部グラフ G = K _2,4を考えます。このグラフには 6 つの頂点A、B、W、X、Y、Zがあり、 AとBはそれぞれW、X、Y、Zのすべてに接続されており、他の頂点は接続されていません。二部グラフとして、G は通常の彩度数が 2 です。つまり、 AとB をある色で塗り、 W、X、Y、Zを別の色で塗っても、隣接する 2 つの頂点が同じ色になることはありません。一方、G のリスト彩度数は 2 よりも大きく、次の構成がそれを示しています。AとBにリスト {赤、青} と {緑、黒} を割り当てます。他の 4 つの頂点にリスト {赤、緑}、{赤、黒}、{青、緑}、{青、黒} を割り当てます。Aのリストから色を選択し、 Bのリストから色を選択しても、両方の選択がすでにその隣接頂点の色付けに使用されている他の頂点が存在します。したがって、G は2 選択可能ではありません。

一方、Gは 3 通りの選択が可能であることは容易にわかります。頂点AとBに任意の色を選択すると、残りの頂点ごとに少なくとも 1 つの色が使用可能になり、これらの色は任意に選択できます。

より一般的には、q を正の整数とし、G を完全二部グラフ K _{q,q ^q}とします。使用可能な色は基数qのq ²つの異なる2桁の数字によって表されます。二部グラフの片側では、最初の桁 iのq通りの選択肢のそれぞれに対して、 q頂点に色のセット{ i 0, i 1, i 2, ... } が与えられ、最初の桁は互いに等しくなります。二部グラフのもう一方の側では、q組 ( a 、 b 、 c 、 ... ) の q q 通りの選択肢のそれぞれに対して、 q 頂点に色のセット {0 a 、 1 b 、 2 c、 ... }^が与えられ、最初の桁はすべて異なります^。図は、q = 3の場合の同じ構築の拡大例を 示しています。

すると、G はLのリストカラーリングを持たない。つまり、二分割の小さい側の頂点にどのような色のセットを選んだとしても、この選択は二分割のもう一方の側の頂点の 1 つの色とすべて競合する。たとえば、色セット {00,01} の頂点が 01 で、色セット {10,11} の頂点が 10 で塗られている場合、色セット {01,10} の頂点は色付けできない。したがって、Gのリスト彩色数は少なくともq + 1である。^[2]

同様に、 の場合、完全な二部グラフK _{n,n は}k選択可能ではありません。 というのは、合計で2 k − 1色が利用可能で、二部グラフの片側で、各頂点が他の各頂点とは異なるk組のこれらの色を利用できるとします。 この場合、二部グラフの各側は少なくともk色を使用する必要があります。これは、 k − 1色のすべてのセットが1 つの頂点のリストから分離されるためです。 片側で少なくともk色が使用され、もう片側で少なくともk色が使用されるため、両側で使用される色が 1 つある必要がありますが、これは 2 つの隣接する頂点が同じ色であることを意味します。 特に、ユーティリティ グラフK _{3,3 の}リスト彩度数は少なくとも 3 であり、グラフK _10,10のリスト彩度数は少なくとも 4 です。^[3]${\displaystyle n={\tbinom {2k-1}{k}},}$

グラフGについて、χ ( G ) を彩色数 、Δ( G )をGの最大次数とします。リスト彩色数ch( G )は次の性質を満たします。

1. ch( G ) ≥ χ ( G )。kリスト彩色可能なグラフは、特に、すべての頂点に同じk色のリストが割り当てられているリスト彩色を持つ必要があり、これは通常のk彩色に対応します。
2. ch( G ) は一般に彩色数で制限されない、つまり、あらゆるグラフGに対してch( G ) ≤ f ( χ ( G ))が成り立つような関数fは存在しない。特に、完全二部グラフの例が示すように、χ ( G ) = 2でありながらch( G )が任意の大きさであるグラフが存在する。^[2]
3. ch( G )≤χ ( G ) ln( n )ここでnはGの頂点数である。^{[4] [5]}
4. ch( G )≤Δ( G )+1 . ^{[3] [6]}
5. Gが平面グラフであればch( G )≤5となる。^[7]
6. Gが二部平面グラフである場合、ch( G )≤3となる。^[8]

文献では 2 つのアルゴリズムの問​​題が検討されています。

1. k選択可能性:与えられたグラフが与えられたkに対してk選択可能かどうかを判定し、
2. ( a、b ) -選択可能性: 与えられたグラフが与えられた関数に対してf選択可能かどうかを判定します。${\displaystyle f:V\to \{a,\dots ,b\}}$

二部グラフのk選択可能性は任意のk ≥ 3に対して -完全であることが知られており、同じことが平面グラフの 4 選択可能性、平面三角形なしグラフの 3 選択可能性、二部平面グラフの (2, 3) 選択可能性にも当てはまります。^{[9] [10]} P ₅フリーグラフ、つまり5 頂点パスグラフを除くグラフの場合、k選択可能性は固定パラメータで扱いやすいです。 ^[11]${\displaystyle \Pi _{2}^{p}}$

グラフが 2 選択可能かどうかを線形時間でテストするには、次数 0 または 1 の頂点を繰り返し削除してグラフの2 コアに到達し、その後は削除ができなくなるまで繰り返し削除します。初期グラフが 2 選択可能であるのは、その 2 コアが偶数サイクルであるか、または 3 つのパスが共通のエンドポイントで形成され、そのうち 2 つのパスの長さが 2 で、3 番目のパスの長さが任意の偶数である場合のみです。 [ ^3]

リストの色分けは、チャネル/周波数の割り当てに関する実際的な問題で発生します。^{[12] [13]}

無料辞書『ウィクショナリー』で「choosability」を調べてください。

• リストのエッジカラーリング

さらに読む

• アイグナー、マーティン。 Ziegler、Günter (2009)、Proofs from THE BOOK (4th ed.)、ベルリン、ニューヨーク: Springer-Verlag、ISBN 978-3-642-00855-9第34章5色平面グラフ。
• Diestel, Reinhard.グラフ理論。第 3 版、Springer、2005 年。第 5.4 章リストの色分け。電子版はダウンロード可能です。