채색 다항식

3개의 꼭지점과 해당 채색 다항식의 모든 비동형 그래프(위부터 시계 방향). 독립 3세트: k³ . 모서리와 단일 꼭지점: k²(k – 1) . 3-경로: k(k – 1)² . 3-클릭: k(k – 1)(k – 2) .

채색 다항식은 수학의 한 분야인 대수적 그래프 이론에서 연구되는 그래프 다항식이다. 색칠할 색상들의 수를 변수로 하는 함수로 그래프 색칠 수를 계산하며 원래 조지 데이비드 버코프가 4색 문제를 연구하기 위해 정의했다. 이것은 해슬러 휘트니와 윌리엄 토머스 텃에 의해 텃 다항식으로 일반화되었으며 이를 통계 물리학의 포츠 모형과 연결했다.

역사

조지 데이비드 버코프는 1912년에 4색 정리를 증명하기 위해 평면 그래프에 대해서만 정의하는 채색 다항식을 도입했다.$P(G,k)$는 $k$개의 색상으로 $G$를 적절하게 채색하는 횟수를 나타내며 모든 평면 그래프 $G$에 대해 $P(G,4)>0$을 보이면 4색 정리를 증명 할 수 있다. 이러한 방식으로 그는 조합 색칠 문제에 대한 다항식의 근을 연구하기 위한 해석학 및 대수학의 강력한 도구를 적용하기를 바랐다.

해슬러 휘트니는 1932년에 버코프의 다항식을 평면 사례에서 일반 그래프로 일반화했다. 1968년 Ronald C. Read는 어떤 다항식이 어떤 그래프의 채색 다항식인지에 대해 질문하고(난제), 채색 동치 그래프의 개념을 도입했다. 오늘날, 채색 다항식은 대수적 그래프 이론의 핵심 대상 중 하나이다.

정의

k 색상을 사용하여 3개의 꼭지점이 있는 꼭지점 그래프의 모든 적절한 꼭지점 색상 지정 $k=0,1,2,3$ . 각 그래프의 채색 다항식은 적절한 색상 수를 통해 보간된다.

그래프 $G$에 대해 $P(G,k)$는 (적절한) 꼭지점 k-채색의 수를 계산한다. 기타 일반적으로 사용되는 표기법은 $P_{G}(k)$, $\chi _{G}(k)$, 또는 $\pi _{G}(k)$과 같다. 임의의 정수 $k\geq 0$에 대한 값이 $P(G,k)$인 유일한 다항식 $P(G,x)$이 존재한다. 이를 $G$의 채색 다항식이라고 한다.

예를 들어 경로 그래프 $P_{3}$에 색상 $k$개를 칠하려면 3개의 꼭지점에서 첫 번째 꼭지점에 대해 $k$ 색상 중 하나를 선택할 수 있다. 두 번째 꼭지점의 나머지 색상 $k-1$개, 마지막으로 세 번째 꼭지점의 두 번째 꼭짓점의 선택과 다른 $k-1$개의 색상 중 하나이다. 그러므로, $P_{3}$의 $k$- 색칠의 수는$P(P_{3},k)=k\cdot (k-1)\cdot (k-1)$이다. 변수 x(반드시 정수일 필요는 없음)에 대해 다음과 같다. $P(P_{3},x)=x(x-1)^{2}=x^{3}-2x^{2}+x$.(색상 순열이나 $G$의 자기동형사상에 의해서만 다른 색상은 여전히 다른 것으로 간주된다.)

삭제-축소

$k$-채색의 수는 $k$에 대한 다항식이라는 사실은 삭제-축소 재귀 또는 기본 환원 정리라고 불리는 재귀 관계에 따른 것이다. 이는 모서리 축소를 기반으로 한다. 한 쌍의 꼭지점 $u$, $v$에 대해 그래프 $G/uv$는 두 꼭지점을 병합하고 그 사이의 모서리를 제거하여 얻는다.$u$와 $v$가 G에서 연결되어 있다면. $G-uv$는 그 모서리 $uv$를 제거하여 얻은 그래프를 나타낸다. 이 그래프의 $k$-채색 수는 다음을 충족한다.

$P(G,k)=P(G-uv,k)-P(G/uv,k)$

마찬가지로, 만약 $u$ 그리고 $v$ $G$에서 인접하지 않고 $G+uv$ 모서리가 있는 그래프이다. $uv$ 추가한 다음

$P(G,k)=P(G+uv,k)+P(G/uv,k)$

이는 $G$의 모든 $k$-채색이 $u$와 $v$에 서로 다른 색상 또는 같은 색을 칠한다는 관찰에서 비롯된다. 첫 번째 경우에 이는$G+uv$의 (적절한) $k$-채색을 제공한다. 두 번째 경우에는 $G/uv$의 채색을 제공한다. 반대로, $G$의 모든 $k$-채색은 $G+uv$ 또는 (모서리 $u$$v$가 없을 경우) $G/uv$의 $k$-채색 부터 유일하게 얻을 수 있다.

따라서 채색 다항식은 다음과 같이 재귀적으로 정의될 수 있다.

n개의 꼭지점을 가지고 모서리는 없는 그래프의 경우$P(G,x)=x^{n}$ 그리고

모서리 $uv$이 있는 그래프 $G$의 경우$P(G,x)=P(G-uv,x)-P(G/uv,x)$

모서리 없는 그래프의 $k$-채색 수는 $k^{n}$이므로, 모든 $G$에 대해 다항식 $P(G,x)$이 모든 정수점 $x=k$에서 $k$-채색수와 일치하는 모서리 수에 대한 귀납법에 의해 얻어진다. 특히, 채색 다항식은 점

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

을 통과하는 최대 n 차의 우일한 보간 다항식이다. 어떤 다른 그래프 불변량이 그러한 재귀를 만족하는지에 대한 텃의 호기심으로 인해 그는 채색 다항식의 이변수 일반화인 텃 다항식 $T_{G}(x,y)$을 발견하게 되었다.

예

특정 그래프에 대한 색다항식

삼각형 $K_{3}$	$x(x-1)(x-2)$
완전한 그래프 $K_{n}$	$x(x-1)(x-2)\cdots (x-(n-1))$
무에지 그래프 ${\overline {K}}_{n}$	$x^{n}$
경로 그래프 $P_{n}$	$x(x-1)^{n-1}$
n개의 꼭지점에 있는 모든 트리	$x(x-1)^{n-1}$
주기 $C_{n}$	$(x-1)^{n}+(-1)^{n}(x-1)$
피터슨 그래프	$x(x-1)(x-2)\left(x^{7}-12x^{6}+67x^{5}-230x^{4}+529x^{3}-814x^{2}+775x-352\right)$

성질

n개의 꼭지점으로 고정된 $G$의 경우, 채색 다항식 $P(G,x)$은 정수 계수를 갖는 n차 일계수 다항식이다.

채색 다항식은 적어도 색수만큼 $G$의 채색성에 관한 정보를 포함한다. 실제로, 채색수는 채색 다항식의 0이 아닌 가장 작은 양의 정수이며,

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

$-1$에서 채색 다항식의 값 $P(G,-1)$은 $(-1)^{|V(G)|}$와 $G$의 비순환 방향의 수를 곱한 값이다.

1에서 계산된 도함수 $P'(G,1)$는 채색 불변량 $\theta (G)$과 절대값이 같다.

<math xmlns="http://www.w3.org/1998/Math/MathML">

<mrow class="MJX-TeXAtom-ORD"> <mstyle scriptlevel="0" displaystyle="true"> <mi>G</mi> </mstyle> </mrow> {\displaystyle G}

</math>$G$에 n개의 꼭지점과 c개의 연결 성분 $G_{1},\ldots ,G_{c}$이 있는 경우,

• $x^{0},\ldots ,x^{c-1}$의 계수는 0이다.
• $x^{c},\ldots ,x^{n}$의 계수는 모두 0이 아니고 부호가 교대한다.
• $x^{n}$의 계수는 1이다(일계수 다항식).
• $x^{n-1}$의 계수는 $-|E(G)|$이다.

$n$ 꼭지점과 $k$ 모서리를 가진 간단한 그래프 $G$의 모서리 수에 대한 귀납법을 통해 이를 증명한다. $k=0$일 때, $G$는 빈 그래프이다. 따라서 정의에 따라 $P(G,x)=x^{n}$. 따라서 $x^{n-1}$의 계수는 $0$이다. 이는 해당 진술이 빈 그래프에 대해 참임을 의미한다. $k=1$일 때, $G$에서와 같이 단 하나의 모서리 $P(G,x)=x^{n}-x^{n-1}$만 갖는다. 따라서 $x^{n-1}$의 계수는 $-1=-|E(G)|$이다. 따라서 명제는 $k=1$에 대해 유지된다. 강한 귀납법을 쓰기 위해 $k=0,1,2,\ldots ,(k-1)$에 대해 진술이 참이라고 가정한다. $G$가 모서리 $k$개를 가지고 있다 하자. 축소-삭제 원리에 의해,

$P(G,x)=P(G-e,x)-P(G/e,x)$

이다. $P(G-e,x)=x^{n}-a_{n-1}x^{n-1}+a_{n-2}x^{n-2}-\cdots$ 이고 $P(G/e,x)=x^{n-1}-b_{n-2}x^{n-2}+b_{n-3}x^{n-3}-\cdots$라 하자. 즉,$P(G,x)=x^{n}-(a_{n-1}+1)x^{n-1}+\cdots$.

$G-e$는 $G$에서 단 하나의 모서리 e를 제거하여 얻어졌으므로 $a_{n-1}=k-1$이고, 그래서 $a_{n-1}+1=k$이고, 따라서 이 진술은 $k$에 대해 참이다.

• $x^{1}$의 계수는 $(-1)^{n-1}$와 선택된 꼭지점에서 유일한 싱크를 갖는 비순환 방향의 수를 곱한 값이다.
• 모든 채색 다항식 계수의 절대값은 로그 오목 수열을 형성한다.
• $\scriptstyle P(G,x)=P(G_{1},x)P(G_{2},x)\cdots P(G_{c},x)$

마지막 성질은 $G$가 $G_{1}$와 $G_{2}$의 클릭-합이면, (즉, $k$ 꼭짓점의 클릭에서 두 개를 붙여서 얻은 그래프)

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

라는 사실로부터 일반화 된다. n개의 꼭지점을 가진 그래프 $G$는 다음과 같은 경우에만 트리이다.

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

채색 동치

위 세 그래프는 채색다항식 $(x-2)(x-1)^{3}x$를 갖는다.

두 그래프가 동일한 채색 다항식을 갖는 경우 채색 동치라고 한다. 동형 그래프는 동일한 채색 다항식을 가지지만, 동형이 아닌 그래프도 채색 동형일 수 있다. 예를 들어 n개의 꼭지점에 있는 모든 트리는 동일한 채색 다항식을 갖는다. 특히, $(x-1)^{3}x$는 클로 그래프와 4개의 꼭지점에 대한 경로 그래프의 채색 다항식이다.

그래프는 채색 다항식에 의해 결정되는 경우 채색적으로 유일하다. 즉, $G$가 채색적으로 유일하면, $P(G,x)=P(H,x)$는 이는 $G$와 $H$가 동형임을 의미한다. 모든 순환 그래프는 채색적으로 유일하다.

채색의 근

"채색 근"이라고 불리는 채색 다항식의 근은 $P(G,x)=0$인 값 x이다. 채색 근은 잘 연구되었다. 사실 버코프가 채색 다항식을 정의하려는 원래 동기는 평면 그래프에 대해 x ≥ 4인 경우 $P(G,x)>0$임을 보여주는 것이었다. 이것이 성공했다면 4색 정리를 증명 했을 것이다.

어떤 그래프도 0색일 수 없으므로 0은 항상 채채색 근이다. 모서리가 없는 그래프만 단색일 수 있으므로 1은 적어도 하나의 모서리가 있는 모든 그래프의 채색 근이다. 반면, 이 두 점을 제외하고는 어떤 그래프도 32/27보다 작거나 같은 실수에서 채색 근을 가질 수 없다. 텃의 결과는 황금비 $\varphi$을 연결한다 채색 근에 대한 연구를 통해 채색 근이 $\varphi ^{2}$과 아주 가까운 곳에 존재함을 보여준다: $G_{n}$가 구의 평면 삼각분할이면

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

따라서 실수선에는 그래프에 대한 채색 근이 없는 큰 부분이 있지만, 복소 평면에 채색 근이 밀집된 무한한 그래프 계열이 존재한다는 의미에서 복소 평면의 모든 점은 채색 근에 임의로 가깝다.

모든 색을 빠짐없이 써서 색칠하기

n개의 꼭짓점을 가진 그래프 $G$에 대해 $e_{k}$를 정확히 $k$개의 색상을 사용하는 채색수라 하자. 따라서 색상의 이름을 바꿔서 서로 얻을 수 있는 채색은 하나로 계산된다. $G$의 자기동형사상으로 얻은 채색은 여전히 별도로 계산된다. 다시 말해서, $e_{k}$는 꼭지점 집합을 $k$ 개의(공집합이 아닌) 독립 집합들로 분할하는 경우의 수를 센다. 그러면 $k!\cdot e_{k}$는 정확히 $k$개의 색상(구별 가능한 색상 포함)을 사용한 채색수를 계산한다. 정수 $x$의 경우, $G$의 모든 $x$-채색은 정수 k ≤ x를 선택하고, 사용 가능한 x 중에서 사용할 $k$ 색상을 선택하고, 정확히 해당 $k$ (구별 가능한) 색상을 사용한 색상을 선택하여 유일하게 얻을 수 있다. 그러므로:

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

여기서 $(x)_{k}=x(x-1)(x-2)\cdots (x-k+1)$는 떨어지는 계승을 나타낸다. 따라서 $e_{k}$는 떨어지는 계승들의 기저 $1,(x)_{1},(x)_{2},(x)_{3},\ldots$에 대한 다항식 $P(G,x)$의 계수들이다.

표준 기저 $1,x,x^{2},x^{3},\ldots$에 대해 $a_{k}$를 $P(G,x)$의 $k$ 번째 계수라 하자. 즉:

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

스털링 수는 표준 기저와 떨어지는 계승 기저 사이의 기저 변환을 제공한다. 이는 다음을 의미한다.

$a_{k}=\sum _{j=0}^{n}(-1)^{j-k}{\begin{bmatrix}j\\k\end{bmatrix}}e_{j}$ 그리고 $e_{k}=\sum _{j=0}^{n}{\begin{Bmatrix}j\\k\end{Bmatrix}}a_{j}.$

분류

색다항식은 Khovanov 호몰로지와 밀접한 관련이 있는 호몰로지 이론에 의해 분류된다.

알고리듬

 

채색 다항식
입력	n개의 꼭지점을 가진 그래프 G
출력	$P(G,x)$의 계수
소요 시간	어떤 상수 $r$에 대해 $O(2^{n}n^{r})$
복잡도	#P-hard
Reduction from	#3SAT

 

#k-colorings
Input	Graph G with n vertices.
Output	$P(G,k)$
Running time	In P for $k=0,1,2$. $O(1.6262^{n})$ for $k=3$. Otherwise $O(2^{n}n^{r})$ for some constant $r$
Complexity	#P-hard unless $k=0,1,2$
Approximability	No FPRAS for $k>2$

채색 다항식과 관련된 계산 문제는 다음과 같다.

• 주어진 그래프 $G$의 채색다항식 $P(G,x)$ 찾기
• 주어진 그래프 $G$에 대해 고정된 x에서 $P(G,x)$ 계산하기

첫 번째 문제는 더 일반적이다. 왜냐하면 $P(G,x)$의 계수를 안다면 차수가 n이기 때문에 모든 정의역에서 다항식 시간 안에 계산 할 수 있다. 두 번째 유형의 문제의 난이도는 $x$값에 크게 좌우되며 계산 복잡도에 대해 집중적으로 연구되었다. $x$가 양의 정수인 경우, 이 문제는 일반적으로 주어진 그래프의 $x$-채색수를 계산하는 것으로 본다. 예를 들어, 여기에는 계산 복잡도 연구의 표준 문제인 3가지 색상의 수를 계산하는 문제 #3-채색이 포함되며 계산복잡도 #P에 대해 완료된다.

효율적인 알고리듬

일부 기본 그래프 클래스의 경우 채색 다항식에 대한 공식이 알려져 있다. 예를 들어 위의 표에 나열된 것처럼 나무와 클릭의 경우에도 마찬가지이다.

다항식 시간 알고리듬은 현 그래프 및 경계 클릭 폭 그래프를 포함하여 더 넓은 종류의 그래프에 대한 채색 다항식을 계산하는 것으로 알려져 있다. 후자의 종류에는 외부 평면 그래프와 같은 경계 트리 너비 의 여그래프 및 그래프가 포함된다.

삭제-축약

삭제-축약 재귀는 삭제-축약 알고리듬이라고 불리는 채색 다항식을 계산하는 방법을 제공한다. 첫 번째 형식(마이너스 포함)에서는 반복이 빈 그래프 모음에서 종료된다. 두 번째 형식(더하기 포함)에서는 완전한 그래프 모음으로 끝난다. 이는 그래프 색상 지정을 위한 많은 알고리듬의 기초를 형성한다. 컴퓨터 대수 시스템 Mathematica의 Combinatorica 패키지에 있는 ChromaticPolynomial 함수는 그래프가 조밀한 경우 두 번째 반복을 사용하고 그래프가 희소한 경우 첫 번째 반복을 사용한다. 두 공식 모두 최악의 경우 실행 시간은 피보나치 수와 동일한 재귀 관계를 만족하므로 n개의 꼭지점과 m개의 모서리를 가진 그래프에서 최악의 경우 알고리듬은 다항식 인수 내에서 시간에 맞춰 실행된다.

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

분석은 입력 그래프의 신장 부분 그래프의 수 $t(G)$의 다항식 인자 안으로 개선될 수 있다. 실제로 일부 재귀 호출을 피하기 위해 분기 및 경계 전략과 그래프 동형사상 거부가 사용되며, 실행 시간은 꼭지점 쌍을 선택하는 데 사용되는 경험적 방법에 따라 달라진다.

큐브 방식

각 꼭지점에 자연수를 할당하면 그래프 색상이 정수 격자의 벡터라는 것을 관찰함으로써 그래프 색상에 대한 자연스러운 기하학적 관점이 있다. 두 꼭지점 $i$, $j$에 동일한 색상을 지정하는 것은 채색 벡터의 $i$번째와 $j$번째 좌표가 동일함과 같으며, 각 모서리는 초평면 $\{x\in \mathbb {R} ^{d}:x_{i}=x_{j}\}$과 연관될 수 있다. 주어진 그래프에 대한 이러한 초평면의 모음을 그래프적 배열이라고 한다. 그래프의 적절한 채색은 금지된 초평면을 피하는 격자점이다.$k$개의 색상들의 집합으로 제한하면, 격자 점이 큐브 $[0,k]^{n}$에 포함된다. 이러한 맥락에서 채색 다항식은 그래픽 배열을 피한 $[0,k]$-큐브안의 격자점의 수를 계산한다.

계산 복잡도

주어진 그래프의 3가지 색상 수를 계산하는 문제는 #P -완전 문제의 표준 예이므로 채색 다항식의 계수를 계산하는 문제는 #P-난해이다. 마찬가지로 주어진 G에 대해 $P(G,3)$를 계산하는 것도 #P-완전이다. 반면에, $k=0,1,2$에 대해 $P(G,k)$를 계산하기는 쉽다. 그래서 해당 문제는 다항식 시간 계산이 가능하다. $k>3$인 정수의 경우 문제는 #P-난해이며, 이는$k=3$인 경우와 유사하게 확립되었다. $P(G,x)$는 세 개의 "쉬운 점"을 제외한 모든 x(음의 정수 및 모든 복소수 포함)에 대해 #P-난해이다. 따라서 #P-난해의 관점에서 채색 다항식 계산의 복잡도가 완전히 이해된다.

전개

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

에서 계수 $a_{n}$는 항상 1과 같고 계수의 다른 여러 속성이 알려져 있다. 이는 일부 계수를 계산하기 쉬운지에 대한 의문을 제기한다. 그러나 고정된 r ≥ 1 와 주어진 그래프 G에 대해 a_r 을 계산하는 계산 문제는 이분 평면 그래프의 경우에도 #P-난해이다.

컴퓨팅을 위한 근사 알고리듬이 없다. $P(G,x)$ 세 가지 쉬운 점을 제외한 모든 $x$로 알려져 있다. 정수점에서 $k=3,4,\ldots$, 주어진 그래프가 k 채색이 될지 결정하는 해당 결정 문제는 NP-난해이다. 이러한 문제는 NP = RP가 아닌 한 제한된 오류 확률 알고리듬을 통해 어떤 곱셈 요소로 근사화될 수 없다, 모든 곱셈 근사법은 값 0과 1을 구별하여 제한된 오류 확률 다항식 시간에 결정 버전을 효과적으로 해결하기 때문이다. 특히, 동일한 가정 하에서 이는 FPRAS(완전 다항식 시간 무작위 근사 방식)의 가능성을 배제한다. NP = RP이 성립하지 않는 한, 임의의 x > 2에 대해 $P(G,x)$를 계산하는 FPRAS가 없다.

참고자료

 

• Biggs, N. (1993), 《Algebraic Graph Theory》, Cambridge University Press, ISBN 978-0-521-45897-9 
• Chao, C.-Y.; Whitehead, E. G. (1978), 〈On chromatic equivalence of graphs〉, 《Theory and Applications of Graphs》, Lecture Notes in Mathematics 642, Springer, 121–131쪽, ISBN 978-3-540-08666-6 
• Dong, F. M.; Koh, K. M.; Teo, K. L. (2005), 《Chromatic polynomials and chromaticity of graphs》, World Scientific Publishing Company, ISBN 978-981-256-317-0 
• Ellis-Monaghan, Joanna A.; Merino, Criel (2011), 〈Graph polynomials and their applications I: The Tutte polynomial〉, Dehmer, Matthias, 《Structural Analysis of Complex Networks》 (영국 영어), 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 3787, Springer-Verlag, 59–68쪽, CiteSeerX 10.1.1.353.6385, doi:10.1007/11604686_6, ISBN 978-3-540-31000-6 
• Goldberg, L.A.; Jerrum, M. (2008), “Inapproximability of the Tutte polynomial”, 《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), “A categorification of the chromatic polynomial”, 《Algebraic & Geometric Topology》 5 (4): 1365–1388, arXiv:math/0412264, doi:10.2140/agt.2005.5.1365, S2CID 1339633 
• Huh, June (2012), “Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs”, 《Journal of the American Mathematical Society》 25 (3): 907–927, arXiv:1008.4749, doi:10.1090/S0894-0347-2012-00731-0, MR 2904577, S2CID 13523955 
• Jackson, B. (1993), “A Zero-Free Interval for Chromatic Polynomials of Graphs”, 《Combinatorics, Probability and Computing》 2 (3): 325–336, doi:10.1017/S0963548300000705, S2CID 39978844 
• Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), “On the computational complexity of the Jones and Tutte polynomials”, 《Mathematical Proceedings of the Cambridge Philosophical Society》 108 (1): 35–53, Bibcode:1990MPCPS.108...35J, doi:10.1017/S0305004100068936, S2CID 121454726 
• Linial, N. (1986), “Hard enumeration problems in geometry and combinatorics”, 《SIAM J. Algebr. Discrete Methods》 7 (2): 331–335, doi:10.1137/0607036 
• Makowsky, J. A.; Rotics, U.; Averbouch, I.; Godlin, B. (2006), 〈Computing graph polynomials on graphs of bounded clique-width〉, 《Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006)》, Lecture Notes in Computer Science 4271, Springer-Verlag, 191–204쪽, CiteSeerX 10.1.1.76.2320, doi:10.1007/11917496_18, ISBN 978-3-540-48381-6 
• Naor, J.; Naor, M.; Schaffer, A. (1987), 〈Fast parallel algorithms for chordal graphs〉, 《Proc. 19th ACM Symp. Theory of Computing (STOC '87)》, 355–364쪽, doi:10.1145/28395.28433, ISBN 978-0897912211, S2CID 12132229 .
• Oxley, J. G.; Welsh, D. J. A. (2002), “Chromatic, flow and reliability polynomials: The complexity of their coefficients.”, 《Combinatorics, Probability and Computing》 11 (4): 403–426, doi:10.1017/S0963548302005175, S2CID 14918970 
• Pemmaraju, S.; Skiena, S. (2003), 《Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica》, Cambridge University Press, section 7.4.2, ISBN 978-0-521-80686-2 
• Read, R. C. (1968), “An introduction to chromatic polynomials” (PDF), 《Journal of Combinatorial Theory》 4: 52–71, doi:10.1016/S0021-9800(68)80087-0 
• Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), 〈Computing the Tutte polynomial of a graph of moderate size〉, Staples, John; Eades, Peter; Katoh, Naoki; Moffat, Alistair, 《Algorithms and Computation, 6th International Symposium, ISAAC '95, Cairns, Australia, December 4–6, 1995, Proceedings》, Lecture Notes in Computer Science 1004, Springer, 224–233쪽, doi:10.1007/BFb0015427, ISBN 978-3-540-60573-7 
• Sokal, A. D. (2004), “Chromatic Roots are Dense in the Whole Complex Plane”, 《Combinatorics, Probability and Computing》 13 (2): 221–261, arXiv:cond-mat/0012369, doi:10.1017/S0963548303006023, S2CID 5549332 
• Stanley, R. P. (1973), “Acyclic orientations of graphs” (PDF), 《Discrete Math.》 5 (2): 171–178, doi:10.1016/0012-365X(73)90108-8 
• Voloshin, Vitaly I. (2002), 《Coloring Mixed Hypergraphs: Theory, Algorithms and Applications.》, American Mathematical Society, ISBN 978-0-8218-2812-0 
• Wilf, H. S. (1986), 《Algorithms and Complexity》, Prentice–Hall, ISBN 978-0-13-021973-2 

외부 링크

• Weisstein, Eric Wolfgang. “Chromatic polynomial”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• PlanetMath Chromatic polynomial 보관됨 2008-08-20 - 웨이백 머신
• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [1]