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

限られた数の許容色によるグラフエッジの色付け

数学における未解決問題

すべてのグラフについて、リスト彩度インデックスは彩度インデックスと等しいですか?

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

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

プロパティ

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

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

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

リスト彩色予想

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

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

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

参考文献

ガルビン、フレッド（1995）、「二部多重グラフのリスト彩色指数」、Journal of Combinatorial Theory、シリーズ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