リスト彩色とリスト彩色予想①

(注意)この記事はディーステル「グラフ理論」の内容をお借りしている部分が多いです。

１、リスト彩色

　グラフGと、その各頂点に対して塗ることが許される色のリストが与えられている。このとき、そのリストから選んだ色を頂点に割り当てて、Gを彩色することをリスト頂点彩色という。すべての頂点にどんなk色のリストを与えても、Gがリストを用いた彩色を持つとき、Gはk-リスト頂点彩色可能、または、k-頂点選択可能であるという。Gがk-頂点選択可能であるような最小のkを、Gのリスト頂点染色数、または、頂点選択数と呼び、ch(G)で表す。

　同様に、辺に対するリスト辺彩色も定義できる。要素数がkのどんなリストを用いても、グラフGを辺彩色できる最小のkを、Gのリスト辺染色数ch1(G)とよぶ。線グラフをL(G)とすれば、ch1(G):=ch( L(G) )である。

　同様に、頂点と辺に対するリスト全彩色を定義できる。要素数がkのどんなリストを用いても、グラフGを全彩色できる最小のkを、Gのリスト全染色数ch2(G)と呼ぶ。全グラフをT(G)とすれば、ch2(G):=ch( T(G) )である。

　原理的に、与えられたグラフがk-選択可能であることを示すことは、k-彩色可能であることを示すことよりも難しい。なぜなら、k-彩色可能は、すべてのリストが(1、2、・・・、k)である場合とみなせるからである。従って、すべてのグラフGに対して、ch(G)≧χ(G)、ch1(G)≧χ1(G)、ch2(G)≧χ2(G)である。