Loading article…
グラフ理論は数学の一分野であり、リスト彩色とは、各頂点を許容される色のリストに制限できるグラフ彩色の一種である。これは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に対して、グラフGは、各頂点vにf ( v )個の色のリストをどのように割り当ててもリスト彩色が可能であれば、f選択可能(またはfリスト彩色可能)である。特に、すべての頂点vに対してf ( v ) = kであれば、f選択可能性はk選択可能性に対応する。
6 つの頂点A、B、W、X、Y、Zを持つ完全二部グラフG = K 2,4を考えます。AとBはそれぞれW、X、Y、Zのすべてに接続されており、他の頂点は接続されていません。二部グラフとして、G は通常の色数 2 を持ちます。AとBを1 つの色で、W、X、Y、Z を別の色で着色しても、隣接する 2 つの頂点が同じ色になることはありません。一方、G は、次の構成で示されるように、リスト色数が 2 より大きいです。AとBにリスト {red, blue} と {green, black} を割り当てます。他の 4 つの頂点にリスト {red, green}、{red, black}、{blue, green}、{blue, black} を割り当てます。Aのリストから色を1つ選び、 Bのリストから色を1つ選ぶと、その2つの選択肢が既に隣接する頂点の色付けに使われている頂点が必ず存在する。したがって、Gは2選択可能ではない。
一方、Gが3選択可能であることは容易にわかる。頂点AとBに任意の色を選択しても、残りの各頂点には少なくとも1つの使用可能な色が残り、これらの色は任意に選択できるからである。
より一般的に、q を正の整数とし、G を完全二部グラフK q,q qとする。使用可能な色は、基数qのq 2種類の異なる 2 桁の数で表されるとする。二部グラフの一方の側では、q個の頂点に、最初の桁iのq通りの選択肢それぞれについて、最初の桁が互いに等しい色の集合 { i 0, i 1, i 2, ... } を与える。二部グラフのもう一方の側では、q q個の頂点に、q タプル ( a , b , c , ... ) のq通りの選択肢それぞれについて、最初の桁がすべて異なる色の集合{ 0 a , 1 b , 2 c , ... } を与える。図は、 q = 3 の場合の同じ構成のより大きな例を示している。
すると、G はLのリスト彩色を持ちません。二分割の小さい側の頂点にどのような色のセットを選択しても、その選択は二分割のもう一方の側のいずれかの頂点のすべての色と競合します。たとえば、色セット {00,01} を持つ頂点が 01 で彩色され、色セット {10,11} を持つ頂点が 10 で彩色された場合、色セット {01,10} を持つ頂点は彩色できません。したがって、Gのリスト彩色数は少なくともq + 1です。[ 2 ]
同様に、すると、完全二部グラフK n,nはk選択可能ではない。なぜなら、合計で2 k − 1色の色が利用可能であり、二部グラフの片側で、各頂点が他の頂点とは異なるk組の色が利用可能であると仮定するからである。この場合、 k − 1色の任意のセットは 1 つの頂点のリストと互いに素であるため、二部グラフの各側は少なくともk色を使用しなければならない。少なくともk色が一方の側で使用され、少なくともk 色がもう一方の側で使用されているため、両方の側で使用される色が 1 つ存在しなければならないが、これは 2 つの隣接する頂点が同じ色を持つことを意味する。特に、効用グラフK 3,3 のリスト彩色数は少なくとも 3 であり、グラフK 10,10 のリスト彩色数は少なくとも 4 である。[ 3 ]
グラフGに対して、χ ( G )を彩色数 、Δ( G )をGの最大次数とする。リスト彩色数ch( G )は次の性質を満たす。
文献では、2つのアルゴリズム問題が検討されている。
二部グラフにおけるk選択可能性は任意のk ≥ 3に対して -完全であり、平面グラフの 4-選択可能性、平面三角形フリーグラフの 3-選択可能性、および二部平面グラフの (2, 3)-選択可能性についても同様である。 [ 9 ] [ 10 ] P 5-フリーグラフ、つまり5 頂点パスグラフを除いたグラフの場合、k-選択可能性は固定パラメータで扱いやすい。 [ 11 ]
グラフが 2-選択可能かどうかは、グラフの2-コアに到達するまで次数が 0 または 1 の頂点を繰り返し削除することで線形時間でテストできます。2-コアに到達した後は、それ以上削除することはできません。初期グラフが 2-選択可能であるのは、その 2-コアが偶数サイクルであるか、または共通の端点を持つ 3 つのパスで構成されるシータグラフであり、2 つのパスの長さが 2 で、3 番目のパスの長さが任意の偶数である場合のみです。[ 3 ]
さらに読む
