彩色多項式

Function in algebraic graph theory

3頂点上のすべての非同型グラフとその彩色多項式（上から時計回り）。独立3集合：k ³。辺と1頂点：k ² ( k − 1)。3パス：k ( k − 1) ²。3クリーク：k ( k − 1)( k − 2)。

彩色多項式は、数学の一分野である代数グラフ理論において研究されるグラフ多項式です。グラフの彩色数を色数の関数として数えるもので、元々はジョージ・デイヴィッド・バーコフによって四色問題を研究するために定義されました。ハスラー・ホイットニーとWTタットによってタット多項式へと一般化され、統計物理学のポッツモデルと結び付けられました。

歴史

ジョージ・デイヴィッド・バーコフは1912年に彩色多項式を導入し、平面グラフに対してのみ定義することで四色定理を証明しようと試みました。 がk色によるGの適切な彩色の数を表すとすれば、すべての平面グラフGに対してを示すことで四色定理が証明できます。このようにして彼は、多項式の根を研究するための解析学と代数学の強力なツールを、組合せ彩色問題に適用しようとしました。 ${\displaystyle P(G,k)}$ ${\displaystyle P(G,4)>0}$

ハスラー・ホイットニーは1932年にバーコフの多項式を平面グラフの場合から一般グラフへと一般化しました。1968年にはロナルド・C・リードが、どの多項式がグラフの彩色多項式であるかを問いましたが、これは未解決の問題であり、彩色的に同値なグラフの概念を導入しました。^{[1]今日、彩色多項式は}代数的グラフ理論の中心的な対象の一つです。^[2]

意味

3頂点グラフのすべての適切な頂点彩色をk色で表したもの。各グラフの彩色多項式は、適切な彩色の個数にわたって補間されます。 ${\displaystyle k=0,1,2,3}$

グラフGにおいて、はその（適切な）頂点k色彩の数を数えます。他によく使われる表記法には、、 、 などがあります。任意の整数k ≥ 0 において評価すると と一致する唯一の多項式があり、これはGの彩色多項式と呼ばれます。 ${\displaystyle P(G,k)}$ ${\displaystyle P_{G}(k)}$ ${\displaystyle \chi _{G}(k)}$ ${\displaystyle \pi _{G}(k)}$ ${\displaystyle P(G,x)}$ ${\displaystyle P(G,k)}$

例えば、3頂点のパスグラフを k色で彩色する場合、最初の頂点にはk色のいずれかを選択し、 2番目の頂点には残りの色のいずれかを選択し、最後に3番目の頂点には2番目の頂点の選択とは異なる色のいずれかを選択します。したがって、はk色彩色数です。変数x（必ずしも整数とは限らない）に対して、k色彩色数は となります。（色の順序やGの自己同型性のみが異なる彩色は、依然として異なる彩色としてカウントされます。） ${\displaystyle P_{3}}$ ${\displaystyle k-1}$ ${\displaystyle k-1}$ ${\displaystyle P(P_{3},k)=k\cdot (k-1)\cdot (k-1)}$ ${\displaystyle P_{3}}$ ${\displaystyle P(P_{3},x)=x(x-1)^{2}=x^{3}-2x^{2}+x}$

削除と短縮

k色の数がkの多項式であるという事実は、削除縮約再帰または基本簡約定理と呼ばれる再帰関係から導かれます。^[3]これは辺縮約に基づいています。頂点のペアとに対して、グラフは2つの頂点を併合し、その間の辺を削除することで得られます。と がGで隣接している場合、辺を削除することで得られるグラフを とします。すると、これらのグラフのk色の数は以下を満たします。 ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G/uv}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G-uv}$ ${\displaystyle uv}$

${\displaystyle P(G,k)=P(G-uv,k)-P(G/uv,k)}$

同様に、Gにおいてと が隣接しておらず、 が辺が追加されたグラフである場合、 ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G+uv}$ ${\displaystyle uv}$

${\displaystyle P(G,k)=P(G+uv,k)+P(G/uv,k)}$

これは、 Gのk色付けはどれも と に異なる色を与えるか、同じ色を与えるかのいずれかであるという観察から導かれます。前者の場合、これは の（適切な） k色付けを与え、後者の場合、 の色付けを与えます。逆に、 Gのk色付けはすべて、またはのk色付けから一意に得られます（ただし、 と がG内で隣接していない場合）。 ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G+uv}$ ${\displaystyle G/uv}$ ${\displaystyle G+uv}$ ${\displaystyle G/uv}$ ${\displaystyle u}$ ${\displaystyle v}$

したがって、彩色多項式は次のように再帰的に定義できる。

${\displaystyle P(G,x)=x^{n}}$n頂点のエッジなしグラフの場合、

${\displaystyle P(G,x)=P(G-uv,x)-P(G/uv,x)}$エッジ（任意に選択）を持つグラフGの場合。 ${\displaystyle uv}$

辺なしグラフのk色彩の数は確かに であるので、辺の数に関する帰納法から、すべてのGに対して、多項式はすべての整数点x  =  kにおけるk色彩の数と一致する。特に、彩色多項式は、点を通るn次の唯一の補間多項式である。 ${\displaystyle k^{n}}$ ${\displaystyle P(G,x)}$

${\displaystyle \left\{(0,P(G,0)),(1,P(G,1)),\ldots ,(n,P(G,n))\right\}.}$

Tutteは、他のどのグラフ不変量がそのような再帰性を満たすのかという好奇心から、彩色多項式の二変数一般化であるTutte 多項式 を発見しました。 ${\displaystyle T_{G}(x,y)}$

例

特定のグラフの彩色多項式

三角形 ${\displaystyle K_{3}}$	${\displaystyle x(x-1)(x-2)}$
完全グラフ ${\displaystyle K_{n}}$	${\displaystyle x(x-1)(x-2)\cdots (x-(n-1))}$
エッジのないグラフ ${\displaystyle {\overline {K}}_{n}}$	${\displaystyle x^{n}}$
パスグラフ ${\displaystyle P_{n}}$	${\displaystyle x(x-1)^{n-1}}$
n頂点の任意の木	${\displaystyle x(x-1)^{n-1}}$
サイクル ${\displaystyle C_{n}}$	${\displaystyle (x-1)^{n}+(-1)^{n}(x-1)}$
ピーターセングラフ	${\displaystyle x(x-1)(x-2)\left(x^{7}-12x^{6}+67x^{5}-230x^{4}+529x^{3}-814x^{2}+775x-352\right)}$

プロパティ

n頂点の固定Gの場合、彩色多項式は整数係数を持つn次単項多項式です。 ${\displaystyle P(G,x)}$

彩色多項式は、彩色数と同程度以上のGの彩色可能性に関する情報を含んでいる。実際、彩色数は彩色多項式の零点ではない最小の正の整数である。

${\displaystyle \chi (G)=\min\{k\in \mathbb {N} :P(G,k)>0\}.}$

多項式を で評価すると、Gの非巡回方向の数の倍数が得られる。^[4] ${\displaystyle -1}$ ${\displaystyle P(G,-1)}$ ${\displaystyle (-1)^{|V(G)|}}$

1 で評価された導関数は、符号までの彩色不変量に等しくなります。 ${\displaystyle P'(G,1)}$ ${\displaystyle \theta (G)}$

Gがn個の頂点とc個の 成分 を持つ場合、 ${\displaystyle G_{1},\ldots ,G_{c}}$

• の係数はゼロです。 ${\displaystyle x^{0},\ldots ,x^{c-1}}$
• の係数はすべてゼロ以外であり、符号が交互に変わります。 ${\displaystyle x^{c},\ldots ,x^{n}}$
• の係数は1 です (多項式は単項式です)。 ${\displaystyle x^{n}}$
• の係数は ${\displaystyle x^{n-1}}$ ${\displaystyle -|E(G)|.}$

これを、頂点と辺を持つ単純グラフGの辺の数に関する帰納法で証明する。 のとき、Gは空グラフである。したがって定義より である。したがって の係数はであり、これは空グラフに対してこの文が成り立つことを意味する。のとき、Gが1つの辺だけを持つ場合のように である。したがって の係数はである。したがって、k = 1に対してこの文が成り立つ。強い帰納法を用いて 、 に対してこの文が成り立つと仮定する。Gに辺があるとする。縮約削除原理により、 ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k=0}$ ${\displaystyle P(G,x)=x^{n}}$ ${\displaystyle x^{n-1}}$ ${\displaystyle 0}$ ${\displaystyle k=1}$ ${\displaystyle P(G,x)=x^{n}-x^{n-1}}$ ${\displaystyle x^{n-1}}$ ${\displaystyle -1=-|E(G)|}$ ${\displaystyle k=0,1,2,\ldots ,(k-1)}$ ${\displaystyle k}$

${\displaystyle P(G,x)=P(G-e,x)-P(G/e,x),}$

とすれば、となる。はGから1 つの辺eを除去することによって得られるので、となり、したがってkに対してこの文が真となる。 ${\displaystyle P(G-e,x)=x^{n}-a_{n-1}x^{n-1}+a_{n-2}x^{n-2}-\cdots ,}$ ${\displaystyle P(G/e,x)=x^{n-1}-b_{n-2}x^{n-2}+b_{n-3}x^{n-3}-\cdots .}$
${\displaystyle P(G,x)=x^{n}-(a_{n-1}+1)x^{n-1}+\cdots }$
${\displaystyle G-e}$ ${\displaystyle a_{n-1}=k-1}$ ${\displaystyle a_{n-1}+1=k}$

• の係数はであり、 は内の三角形 (3 循環サブグラフ) の数です。 ${\displaystyle x^{n-2}}$ ${\displaystyle {\tbinom {|E|}{2}}-t(G)}$ ${\displaystyle t(G)}$ ${\displaystyle G}$

• の係数は、指定された任意に選ばれた頂点において、一意のシンクを持つ非巡回方向の数の積である。^[5] ${\displaystyle x^{1}}$ ${\displaystyle (-1)^{n-1}}$
• すべての彩色多項式の係数の絶対値は対数凹列を形成する。^[6]
• ${\displaystyle P(G,x)=P(G_{1},x)\,P(G_{2},x)\cdots P(G_{c},x)}$

最後の性質は、Gがと（すなわち、2つをk頂点のクリークで接着して得られるグラフで、完全グラフと同型である）のkクリーク和である場合、 ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle K_{k}}$

${\displaystyle P(G,x)={\frac {P(G_{1},x)P(G_{2},x)}{P(K_{k},x)}}={\frac {P(G_{1},x)P(G_{2},x)}{x(x-1)\cdots (x-k+1)}}.}$

n個の頂点を持つグラフGが木となるのは、

${\displaystyle P(G,x)=x(x-1)^{n-1}.}$

色彩等価性

彩色多項式が に等しい 3 つのグラフ。 ${\displaystyle (x-2)(x-1)^{3}x}$

2つのグラフが同じ彩色多項式を持つ場合、それらは彩色的に同値であると言われます。同型グラフは同じ彩色多項式を持ちますが、同型でないグラフでも彩色的に同値になる場合があります。例えば、 n頂点を持つすべての木は同じ彩色多項式を持ちます。特に、 4頂点を持つクローグラフとパスグラフの両方の彩色多項式は です。 ${\displaystyle (x-1)^{3}x}$

グラフが彩色的に一意であるとは、同型性を除いて、その彩色多項式によって決定される場合である。言い換えれば、Gが彩色的に一意であれば、GとHは同型であることを意味する。すべての閉路グラフは彩色的に一意である。^[7] ${\displaystyle P(G,x)=P(H,x)}$

半音の根音

彩色多項式の根（または零）は「彩色根」と呼ばれ、 となる値xです。彩色根はよく研究されており、実際、バーコフが彩色多項式を定義した当初の動機は、平面グラフにおいてx ≥ 4となることを示すことでした。これにより、四色定理が確立されたはずです。 ${\displaystyle P(G,x)=0}$ ${\displaystyle P(G,x)>0}$

グラフは0色にはなり得ないので、0は常に彩色根となる。辺のないグラフのみが1色にできるため、少なくとも1つの辺を持つすべてのグラフの1は彩色根となる。一方、これら2点を除いて、32/27以下の実数に彩色根を持つグラフは存在しない。^[8] Tutteの結果は、黄金比 と彩色根の研究を結び付け、彩色根が に非常に近いところに存在することを示している。が球面の平面三角形分割である 場合、 ${\displaystyle \varphi }$ ${\displaystyle \varphi ^{2}}$ ${\displaystyle G_{n}}$

${\displaystyle P(G_{n},\varphi ^{2})\leq \varphi ^{5-n}.}$

このように実数直線にはどのグラフに対しても彩色根を含まない部分が大きいが、複素平面上のすべての点は、複素平面上に彩色根が稠密であるグラフの族が無限に存在するという意味で、彩色根に任意に近い。^[9]

すべての色を使った塗り絵

n頂点のグラフGについて、色の名前を変更するまで正確にk色を使用した彩色の数を で表します(したがって、色を並べ替えることで互いに得られる彩色は 1 としてカウントされますが、Gの自己同型によって得られる彩色は依然として別々にカウントされます)。言い換えると、頂点セットをk 個(空でない)の独立集合に分割する回数を数えます。次に、正確にk色 (区別可能な色を使用)を使用した彩色の数を数えます。整数xについて、Gのすべてのx彩色は、整数k ≤ xを選択し、使用可能なxから使用するk色を選択し、それらのk色 (区別可能な) 色を使用した彩色を行うことで一意に取得できます。したがって、 ${\displaystyle e_{k}}$ ${\displaystyle e_{k}}$ ${\displaystyle k!\cdot e_{k}}$

${\displaystyle P(G,x)=\sum _{k=0}^{x}{\binom {x}{k}}k!\cdot e_{k}=\sum _{k=0}^{x}(x)_{k}\cdot e_{k},}$

ここで、 は階乗降順を表します。したがって、これらの数値は階乗降順の基底における多項式の係数です。 ${\displaystyle (x)_{k}=x(x-1)(x-2)\cdots (x-k+1)}$ ${\displaystyle e_{k}}$ ${\displaystyle P(G,x)}$ ${\displaystyle 1,(x)_{1},(x)_{2},(x)_{3},\ldots }$

を標準基底 におけるのk番目の係数とすると、次の式が成り立ちます。 ${\displaystyle a_{k}}$ ${\displaystyle P(G,x)}$ ${\displaystyle 1,x,x^{2},x^{3},\ldots }$

${\displaystyle P(G,x)=\sum _{k=0}^{n}a_{k}x^{k}}$

スターリング数は、標準基底と階乗降基底の間の基底の変化を与えます。これは以下のことを意味します。

${\displaystyle a_{k}=\sum _{j=0}^{n}(-1)^{j-k}{\begin{bmatrix}j\\k\end{bmatrix}}e_{j}}$   そして   ${\displaystyle e_{k}=\sum _{j=0}^{n}{\begin{Bmatrix}j\\k\end{Bmatrix}}a_{j}.}$

分類

彩色多項式はコバノフホモロジーと密接に関連するホモロジー理論によって分類される。^[10]

アルゴリズム

彩色多項式
入力	n個の頂点を持つグラフG。
出力	係数 ${\displaystyle P(G,x)}$
実行時間	${\displaystyle O(2^{n}n^{r})}$一定の ${\displaystyle r}$
複雑	#P -ハード
削減額	#3SAT

#k-カラーリング
入力	n個の頂点を持つグラフG。
出力	${\displaystyle P(G,k)}$
実行時間	Pにおいて、 の場合。の場合 。 それ以外の場合、ある定数 ${\displaystyle k=0,1,2}$ ${\displaystyle O(1.6262^{n})}$ ${\displaystyle k=3}$ ${\displaystyle O(2^{n}n^{r})}$ ${\displaystyle r}$
複雑	#P -hard がない限り ${\displaystyle k=0,1,2}$
近似可能性	FPRASは適用されません ${\displaystyle k>2}$

彩色多項式に関連する計算上の問題には以下が含まれる。

• 与えられたグラフGの彩色多項式を求める。 ${\displaystyle P(G,x)}$
• 与えられたGに対して固定されたxで評価します。 ${\displaystyle P(G,x)}$

最初の問題はより一般的な問題です。なぜなら、 の係数が分かれば、次数がnなので、多項式時間で任意の時点で評価できるからです。2つ目のタイプの問題の難しさはxの値に大きく依存し、計算複雑性の研究において精力的に研究されてきました。xが自然数の場合、この問題は通常、与えられたグラフのx色彩の数を計算する問題とみなされます。例えば、これには、3色彩彩の数を数える問題#3-coloringが含まれます。これは、計数複雑性の研究における標準的な問題であり、計数クラス #Pについて完全です。 ${\displaystyle P(G,x)}$

効率的なアルゴリズム

いくつかの基本グラフクラスでは、彩色多項式の閉式が知られています。例えば、上の表に示すように、木やクリークの場合も同様です。

多項式時間アルゴリズムは、弦グラフ^[11]や制限されたクリーク幅のグラフを含む、より広いクラスのグラフの彩色多項式を計算するために知られています。^[12]後者のクラスには、コグラフや、外平面グラフなどの制限されたツリー幅のグラフが含まれます。

削除と短縮

削除-縮約再帰は、彩色多項式を計算する方法であり、削除-縮約アルゴリズムと呼ばれます。最初の形式（マイナス付き）では、再帰は空グラフのコレクションで終了します。2番目の形式（プラス付き）では、完全グラフのコレクションで終了します。これは、グラフの色付けのための多くのアルゴリズムの基礎を形成します。コンピュータ代数システムMathematicaのCombinatoricaパッケージのChromaticPolynomial関数は、グラフが密な場合は2番目の再帰を使用し、グラフが疎な場合は1番目の再帰を使用します。^{[13]どちらの式でも、最悪の場合の実行時間は}フィボナッチ数と同じ再帰関係を満たすため、最悪の場合、アルゴリズムは多項式因数の時間内で実行されます。

${\displaystyle \varphi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1.62^{n+m}\right),}$

n頂点m辺のグラフ上で行われます。^[14]解析は入力グラフの全域木の数の多項式係数以内で改善できます。 ^[15]実際には、分岐限定法とグラフ同型性拒絶法が再帰呼び出しを避けるために採用されていますが、実行時間は頂点ペアの選択に使用されるヒューリスティックに依存します。 ${\displaystyle t(G)}$

キューブ法

グラフ彩色については、各頂点に自然数を割り当てることで、グラフ彩色が整数格子のベクトルになることを観察することにより、自然な幾何学的観点が得られます。2 つの頂点とに同じ色が割り当てられることは、彩色ベクトルの番目と番目の座標が等しいことと同等であるため、各辺は の形式を持つ超平面に関連付けることができます。特定のグラフに対するこのような超平面の集合は、そのグラフのグラフィック配置と呼ばれます。グラフの適切な彩色とは、禁制超平面を回避する格子点のことです。色の集合に制限すると、格子点は立方体 に含まれます。この文脈では、彩色多項式は、グラフィック配置を回避する -立方体内の格子点の数を数えます。 ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \{x\in \mathbb {R} ^{d}:x_{i}=x_{j}\}}$ ${\displaystyle k}$ ${\displaystyle [0,k]^{n}}$ ${\displaystyle [0,k]}$

計算の複雑さ

与えられたグラフの 3-彩色数を計算する問題は、#P完全問題の標準的な例であるため、彩色多項式の係数を計算する問題は #P 困難です。同様に、与えられたGについての評価は#P 完全です。一方、については を計算するのは簡単なので、対応する問題は多項式時間で計算可能です。整数については、この問題は #P 困難であり、これは の場合と同様に成立します。実際、3 つの「簡単な点」を除くすべてのx (負の整数やすべての複素数を含む)について は #P 困難であることが知られています。 ^[16]このように、#P 困難性の観点からは、彩色多項式の計算の複雑さは完全に理解されています。 ${\displaystyle P(G,3)}$ ${\displaystyle k=0,1,2}$ ${\displaystyle P(G,k)}$ ${\displaystyle k>3}$ ${\displaystyle k=3}$ ${\displaystyle P(G,x)}$

拡大の中で

${\displaystyle P(G,x)=a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n},}$

係数は常に1であり、係数の他のいくつかの性質は既知である。このことから、係数のいくつかは計算が容易なのかどうかという疑問が生じる。しかし、r ≥ 1を固定し、与えられたグラフGに対してa _rを計算する計算問題は、二部平面グラフであっても#P困難である。^[17] ${\displaystyle a_{n}}$

3つの容易な点を除いて、任意のxに対して計算を行う近似アルゴリズムは知られていない。整数点において、与えられたグラフがk色であるかどうかを判断する対応する決定問題はNP困難である。このような問題は、NP = RPでない限り、有限誤差確率アルゴリズムによって任意の乗法係数に近似することはできない。なぜなら、任意の乗法近似は値0と1を区別し、事実上、有限誤差確率多項式時間で決定バージョンを解くことになるからである。特に、同じ仮定の下では、これは完全な多項式時間ランダム近似スキーム（FPRAS）の可能性を排除する。NP  =  RPが成り立たない限り、任意のx > 2を計算するためのFPRASは存在しない。^[18] ${\displaystyle P(G,x)}$ ${\displaystyle k=3,4,\ldots }$ ${\displaystyle P(G,x)}$

参照

• 色対称関数

注記

1. 読む (1968)
2. いくつかの章 Biggs (1993)
3. ドン、コー、テオ（2005）
4. スタンリー（1973）
5. エリス・モナハン＆メリノ（2011）
6. えっ（2012）
7. チャオ＆ホワイトヘッド（1978）
8. ジャクソン（1993）
9. ソーカル（2004）
10. ヘルメ・ギゾン＆ロン（2005）
11. ナオール、ナオール、シェーファー (1987)。
12. ヒメネス、フリニニー、ノイ (2005);マコウスキーら。 （2006年）。
13. ペマラジュ＆スキエナ（2003）
14. ウィルフ（1986）
15. 関根・今井・谷（1995）
16. Jaeger、Vertigan、Welsh (1990)、(Linial 1986)の縮小に基づく。
17. オクスリー＆ウェルシュ（2002）
18. ゴールドバーグ＆ジェラム（2008）

参考文献

• Biggs, N. (1993),代数的グラフ理論, Cambridge University Press, ISBN 978-0-521-45897-9
• Chao, C.-Y.; Whitehead, EG (1978)、「グラフの彩色同値性について」、グラフの理論と応用、数学講義ノート、第642巻、Springer、pp.  121– 131、ISBN 978-3-540-08666-6
• Dong, FM; Koh, KM; Teo, KL (2005),彩色多項式とグラフの彩度, World Scientific Publishing Company, ISBN 978-981-256-317-0
• エリス・モナハン、ジョアンナ・A. ; メリノ、クリエル (2011)、「グラフ多項式とその応用 I: タット多項式」、デマー、マティアス (編)、『複雑ネットワークの構造分析』、arXiv : 0803.3079、doi :10.1007/978-0-8176-4789-6_9、ISBN 978-0-8176-4789-6、S2CID  585250
• Giménez, O.; Hliněný, P.; Noy, M. (2005), "Computing the Tutte polynomial on graphs of bounded clique-width", Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005) , Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, pp.  59– 68, CiteSeerX  10.1.1.353.6385 , doi :10.1007/11604686_6, ISBN 978-3-540-31000-6
• Goldberg, LA ; Jerrum, M. (2008)、「Tutte多項式の近似不可能性」、Information and Computation、206 (7): 908、arXiv : cs/0605140、doi :10.1016/j.ic.2008.04.003、S2CID  53304001
• Helme-Guizon, Laure; Rong, Yongwu (2005)、「彩色多項式の分類」、Algebraic & Geometric Topology、5 (4): 1365– 1388、arXiv : math/0412264、doi :10.2140/agt.2005.5.1365、S2CID  1339633
• Huh, June (2012)、「射影超曲面のミルナー数とグラフの彩色多項式」、アメリカ数学会誌、25 (3): 907– 927、arXiv : 1008.4749、doi :10.1090/S0894-0347-2012-00731-0、MR  2904577、S2CID  13523955
• ジャクソン, B. (1993)、「グラフの彩色多項式の零点自由区間」、組合せ論、確率論、計算、2 (3): 325– 336、doi :10.1017/S0963548300000705、S2CID  39978844
• イェーガー, F.; ヴァーティガン, DL; ウェルシュ, DJA (1990)「ジョーンズ多項式とタット多項式の計算複雑性について」ケンブリッジ哲学協会数学紀要、108 (1): 35– 53、Bibcode :1990MPCPS.108...35J、doi :10.1017/S0305004100068936、S2CID  121454726
• Linial, N. (1986)、「幾何学と組合せ論における困難な列挙問題」、SIAM J. Algebr. Discrete Methods、7 (2): 331– 335、doi :10.1137/0607036
• Makowsky, JA; Rotics, U.; Averbouch, I.; Godlin, B. (2006)、「境界付きクリーク幅のグラフにおけるグラフ多項式の計算」、Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006)、Lecture Notes in Computer Science、vol. 4271、Springer-Verlag、pp.  191– 204、CiteSeerX  10.1.1.76.2320、doi :10.1007/11917496_18、ISBN 978-3-540-48381-6
• ナオール、J.ナオール、M. Ｓｃｈａｆｆｅｒ、Ａ．（１９８７）、「弦グラフのための高速並列アルゴリズム」、Ｐｒｏｃ．第19回ACMシンプ。 Theory of Computing (STOC '87)、pp.  355–364、doi : 10.1145/28395.28433、ISBN 978-0897912211、S2CID  12132229。
• Oxley, JG; Welsh, DJA (2002)、「彩色多項式、フロー多項式、信頼性多項式：その係数の複雑さ」、組合せ論、確率論、計算、11 (4): 403– 426、doi :10.1017/S0963548302005175、S2CID  14918970
• Pemmaraju, S.; Skiena, S. (2003)、『計算離散数学：Mathematicaによる組合せ論とグラフ理論』、ケンブリッジ大学出版局、セクション7.4.2、ISBN 978-0-521-80686-2
• Read, RC (1968)、「彩色多項式入門」(PDF)、Journal of Combinatorial Theory、4 : 52– 71、doi : 10.1016/S0021-9800(68)80087-0
• 関根京子、今井博、谷誠一郎 (1995)、「中規模グラフの Tutte 多項式の計算」、Staples, John、Eades, Peter、加藤直樹、Moffat, Alistair (編)、アルゴリズムと計算、第 6 回国際シンポジウム、ISAAC '95、ケアンズ、オーストラリア、1995 年 12 月 4 日～6 日、議事録、Lecture Notes in Computer Science、第 1004 巻、Springer、pp.  224～ 233、doi :10.1007/BFb0015427、ISBN 978-3-540-60573-7
• ソーカル, AD (2004)、「彩色根は複素平面全体で稠密である」、組合せ論、確率論、計算、13 (2): 221– 261、arXiv : cond-mat/0012369、doi :10.1017/S0963548303006023、S2CID  5549332
• スタンリー, RP (1973)、「グラフの非巡回的配向」(PDF)、離散数学、5 (2): 171– 178、doi :10.1016/0012-365X(73)90108-8
• Voloshin, Vitaly I. (2002) 「混合ハイパーグラフの色付け：理論、アルゴリズム、応用」アメリカ数学会、ISBN 978-0-8218-2812-0
• Wilf, HS (1986),アルゴリズムと複雑性, Prentice–Hall, ISBN 978-0-13-021973-2

外部リンク

• ワイススタイン、エリック W.、「彩色多項式」、MathWorld
• PlanetMathの彩色多項式。
• Gary Haggard、David J. Pearce、Gordon RoyleによるTutte多項式、Chromatic多項式、Flow多項式を計算するコード: [1]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Chromatic_polynomial&oldid=1305713352"