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

グラフ理論において、リスト エッジ カラーリングは、リスト カラーリングとエッジ カラーリングを組み合わせたグラフ カラーリングの一種です。リスト エッジ カラーリング問題のインスタンスは、グラフと、各エッジに許可されている色のリストで構成されます。リスト エッジ カラーリングは、許可されている色のリストから各エッジの色を選択することです。隣接する 2 つのエッジが同じ色にならない場合、カラーリングは適切です。

グラフGがk辺選択可能であるとは、 G を基礎グラフとして持ち、 Gの各辺に少なくともk色の許容色を提供するリスト辺彩色のすべてのインスタンスが適切な彩色を持つ場合です。グラフ G の辺選択可能性、またはリスト辺彩色可能性、リスト辺彩色数、またはリスト彩色指数、ch'( G )は、 Gがk辺選択可能であるような最小の数kです。これは常に彩色指数に等しいと予想されます。

ch'( G )のいくつかの性質:

1. ${\displaystyle \operatorname {ch} '(G)<2\chi '(G).}$
2. ${\displaystyle \operatorname {ch} '(K_{n,n})=n.}$これは、Galvin (1995) によって証明されたDinitz 予想 です。
3. ${\displaystyle \operatorname {ch} '(G)<(1+o(1))\chi '(G),}$つまり、リスト彩度指数と彩度指数は漸近的に一致する (Kahn 2000)。

ここで、χ ′ ( G )はGの彩色インデックス、K _n,nは等しい部分集合を持つ完全な二部グラフです。

リストの辺の色付けに関する最も有名な未解決問題は、おそらくリストの色付け予想でしょう。

$${\displaystyle \operatorname {ch} '(G)=\chi '(G).}$$

この予想の起源は曖昧です。Jensen & Toft (1995) がその歴史を概観しています。Galvin (1995) によって証明された Dinitz 予想は、完全な二部グラフ K _n,nに対するリスト彩色予想の特殊なケースです。

• ガルビン、フレッド(1995)、「二部多重グラフのリスト彩色指数」、組み合わせ理論ジャーナル、シリーズ B、63 : 153–158、doi : 10.1006/jctb.1995.1011。
• ジェンセン、トミー R.; トフト、ビャーネ (1995)、「12.20 リストエッジ彩色数」、グラフカラーリング問題、ニューヨーク: ワイリーインターサイエンス、pp. 201–202、ISBN 0-471-02865-7。
• カーン、ジェフ（2000）、「マルチグラフのリスト彩色指数の漸近解析」、ランダム構造とアルゴリズム、17（2）：117–156、doi：10.1002 / 1098-2418（200009）17：2<117：：AID-RSA3>3.0.CO;2-9