채색 다항식 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Chromatic_polynomial_of_all_3-vertex_graphs_BW.png|오른쪽|섬네일|447x447픽셀| 3개의 꼭지점과 해당 채색 다항식의 모든 비동형 그래프(위부터 시계 방향). 독립 3세트: {{수학|''k''{{sup|3}}}} . 모서리와 단일 꼭지점: {{수학|''k''{{sup|2}}(''k'' – 1)}} . 3-경로: {{수학|''k''(''k'' – 1){{sup|2}}}} . 3-클릭: {{수학|''k''(''k'' – 1)(''k'' – 2)}} .]]
'''채색 다항식'''(chromatic polynomial)은 [[수학]]의 한 분야인 [[대수적 그래프 이론]]에서 연구되는 그래프 다항식이다. 색칠할 색상들의 수를 변수로 하는 함수로 [[그래프 색칠]] 수를 계산하며 원래 [[조지 데이비드 버코프]]가 [[4색 정리|4색 문제]]를 연구하기 위해 정의했다. 이것은 [[해슬러 휘트니]]와 [[윌리엄 토머스 텃]]에 의해 [[텃 다항식]]으로 일반화되었으며 이를 [[통계역학|통계 물리학]]의 [[포츠 모형]]과 연결했다.

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

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

== 정의 ==
[[파일:Chromatic_polynomial_of_all_3-vertex_graphs_BW_with_colorings.png|오른쪽|섬네일|383x383픽셀| ''k'' 색상을 사용하여 3개의 꼭지점이 있는 꼭지점 그래프의 모든 적절한 꼭지점 색상 지정 <math>k=0,1,2,3</math> . 각 그래프의 채색 다항식은 적절한 색상 수를 통해 보간된다.]]
그래프 ''<math>G</math>''에 대해 <math>P(G,k)</math>는 (적절한) [[그래프 색칠|꼭지점 ''k''-채색]]의 수를 계산한다. 기타 일반적으로 사용되는 표기법은 <math>P_G(k)</math>, <math>\chi_G(k)</math>, 또는 <math>\pi_G(k)</math>과 같다. 임의의 정수 <math>k\geq0</math>에 대한 값이 <math>P(G,k)</math>인 유일한 [[다항식]] <math>P(G,x)</math>이 존재한다. 이를 ''<math>G</math>''의 '''채색 다항식'''이라고 한다.

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

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

: <math>P(G,k)=P(G-uv, k)- P(G/uv,k)</math>

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

: <math>P(G,k)= P(G+uv, k) + P(G/uv,k)</math>

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

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

: ''n개의'' 꼭지점을 가지고 모서리는 없는 그래프의 경우<math>P(G,x)=x^n</math> 그리고
: 모서리 <math>uv</math>이 있는 그래프 ''<math>G</math>''의 경우<math>P(G,x)=P(G-uv, x)- P(G/uv,x)</math>

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

: <math>\left \{ (0, P(G, 0)), (1, P(G, 1)), \ldots, (n, P(G, n)) \right \}.</math>

을 통과하는 최대 ''n'' 차의 우일한 보간 다항식이다. 어떤 다른 그래프 불변량이 그러한 재귀를 만족하는지에 대한 [[윌리엄 토머스 텃|텃]]의 호기심으로 인해 그는 채색 다항식의 이변수 일반화인 [[텃 다항식]] <math>T_G(x,y)</math>을 발견하게 되었다.

== 예 ==
{| class="wikitable"
|+특정 그래프에 대한 색다항식
| 삼각형 <math>K_3</math>
| <math>x(x-1)(x-2)</math>
|-
| [[완전 그래프|완전한 그래프]] <math>K_n</math>
| <math>x(x-1)(x-2)\cdots(x-(n-1))</math>
|-
| 무에지 그래프 <math>\overline K_n</math>
| <math>x^n</math>
|-
| [[경로 그래프]] <math>P_n</math>
| <math>x(x-1)^{n-1}</math>
|-
| ''n개의'' 꼭지점에 있는 모든 [[나무 그래프|트리]]
| <math>x(x-1)^{n-1}</math>
|-
| [[순환 그래프|주기]] <math>C_n</math>
| <math>(x-1)^n+(-1)^n(x-1)</math>
|-
| [[페테르센 그래프|피터슨 그래프]]
| <math>x(x-1)(x-2) \left (x^7-12x^6+67x^5-230x^4+529x^3-814x^2+775x-352 \right)</math>
|}

== 성질 ==
''n개의'' 꼭지점으로 고정된 ''<math>G</math>''의 경우, 채색 다항식 <math>P(G, x)</math>은 정수 계수를 갖는 ''n''차 [[일계수 다항식|일계수]] 다항식이다.

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

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

<math>-1</math>에서 채색 다항식의 값 <math>P(G,-1)</math>은 <math>(-1)^{|V(G)|}</math>와 ''<math>G</math>''의 비순환 방향의 수를 곱한 값이다.<ref>{{하버드 인용 본문|Stanley|1973}}</ref>

1에서 계산된 도함수 <math>P'(G, 1)</math>는 [[Chromatic invariant|채색 불변량]] <math>\theta(G)</math>과 절대값이 같다.

''<span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;">&lt;math xmlns="http://www.w3.org/1998/Math/MathML"&gt;

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

&lt;/math&gt;</span><math>G</math>에'' ''n개의'' 꼭지점과 ''c개의'' [[연결 요소 (그래프 이론)|연결 성분]] <math>G_1, \ldots, G_c</math>이 있는 경우,

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

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

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

* <math>x^1</math>의 계수는 <math>(-1)^{n-1}</math>와 선택된 꼭지점에서 유일한 싱크를 갖는 비순환 방향의 수를 곱한 값이다.<ref>{{하버드 인용 본문|Ellis-Monaghan|Merino|2011}}</ref>
* 모든 채색 다항식 계수의 절대값은 로그 오목 수열을 형성한다.<ref>{{하버드 인용 본문|Huh|2012}}</ref>
* <math>\scriptstyle P(G, x) = P(G_1, x)P(G_2,x) \cdots P(G_c,x)</math>

마지막 성질은 ''<math>G</math>''가 <math>G_1</math>와 <math>G_2</math>의 클릭-합이면, (즉, ''<math>k</math>'' 꼭짓점의 클릭에서 두 개를 붙여서 얻은 그래프)

: <math>P(G, x) = \frac{P(G_1,x)P(G_2,x)}{x(x-1)\cdots(x-k+1)}.</math>

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

: <math>P(G, x) = x(x-1)^{n-1}.</math>

=== 채색 동치 ===
[[파일:Chromatically_equivalent_graphs.svg|오른쪽|섬네일|256x256픽셀|{{중앙|위 세 그래프는 채색다항식 <math>(x-2)(x-1)^3x</math>를 갖는다.}}]]
두 그래프가 동일한 채색 다항식을 갖는 경우 ''채색 동치''라고 한다. 동형 그래프는 동일한 채색 다항식을 가지지만, 동형이 아닌 그래프도 채색 동형일 수 있다. 예를 들어 ''n''개의 꼭지점에 있는 모든 트리는 동일한 채색 다항식을 갖는다. 특히, <math>(x-1)^3x</math>는 클로 그래프와 4개의 꼭지점에 대한 [[경로 그래프]]의 채색 다항식이다.

그래프는 채색 다항식에 의해 결정되는 경우 ''채색적으로 유일하다''. 즉, ''<math>G</math>가'' 채색적으로 유일하면, <math>P(G, x) = P(H, x)</math>는 이는 ''<math>G</math>''와 ''<math>H</math>''가 동형임을 의미한다. 모든 [[순환 그래프]]는 채색적으로 유일하다.<ref>{{하버드 인용 본문|Chao|Whitehead|1978}}</ref>

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

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

: <math>P(G_n,\varphi^2) \leq \varphi^{5-n}.</math>

따라서 실수선에는 그래프에 대한 채색 근이 없는 큰 부분이 있지만, 복소 평면에 채색 근이 밀집된 무한한 그래프 계열이 존재한다는 의미에서 [[복소평면|복소 평면]]의 모든 점은 채색 근에 임의로 가깝다.<ref>{{하버드 인용 본문|Sokal|2004}}</ref>

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

: <math>P(G,x) = \sum_{k=0}^x \binom{x}{k} k! \cdot e_k = \sum_{k=0}^x (x)_k \cdot e_k,</math>

여기서 <math>(x)_k = x(x-1)(x-2)\cdots(x-k+1)</math>는 떨어지는 계승을 나타낸다. 따라서 <math>e_k</math>는 떨어지는 계승들의 기저 <math>1,(x)_1,(x)_2,(x)_3,\ldots</math>에 대한 다항식 <math>P(G,x)</math>의 계수들이다.

표준 기저 <math>1,x,x^2,x^3,\ldots</math>에 대해 <math>a_k</math>를 <math>P(G,x)</math>의 ''<math>k</math>'' 번째 계수라 하자. 즉:

: <math>P(G,x) = \sum_{k=0}^n a_k x^k</math>

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

: <math>a_k = \sum_{j=0}^n (-1)^{j-k} \begin{bmatrix}j\\k\end{bmatrix} e_j</math>&nbsp;그리고&nbsp;<math>e_k = \sum_{j=0}^n \begin{Bmatrix}j\\k\end{Bmatrix} a_j. </math>

=== 분류 ===
색다항식은 Khovanov 호몰로지와 밀접한 관련이 있는 [[호몰로지]] 이론에 의해 분류된다.<ref>{{하버드 인용 본문|Helme-Guizon|Rong|2005}}</ref>

== 알고리듬 ==
 {{infobox|above=채색 다항식|abovestyle=background: #DD9; font-size: 125%;|labelstyle=font-weight:normal|label1=입력|data1=''n''개의 꼭지점을 가진 그래프 ''G''|label2=출력|data2=<math>P(G, x)</math>의 계수|label3=소요 시간|data3=어떤 상수 <math>r</math>에 대해 <math>O(2^nn^r)</math>|label4=복잡도|data4=[[Sharp-P|#P]]-hard|label5=Reduction from|data5=<nowiki>#</nowiki>3SAT}} {{infobox|above=<nowiki>#</nowiki>k-colorings|abovestyle=background: #DD9; font-size: 125%;|labelstyle=font-weight:normal|label1=Input|data1=Graph ''G'' with ''n'' vertices.|label2=Output|data2=<math>P(G, k)</math>|label3=Running time|data3=In [[P (complexity class)|P]] for <math>k=0,1,2</math>. <math>O(1.6262^n)</math> for  <math>k=3</math>. Otherwise
<math>O(2^nn^r)</math> for some constant <math>r</math>|label4=Complexity|data4=[[Sharp-P|#P]]-hard unless <math>k=0,1,2</math>|label5=Approximability|data5=No FPRAS for <math>k>2</math>}}

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

* 주어진 그래프 ''<math>G</math>''의 채색다항식 <math>P(G, x)</math> 찾기
* 주어진 그래프 ''<math>G</math>''에 대해 고정된 x에서 <math>P(G, x)</math> 계산하기

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

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

다항식 시간 알고리듬은 [[현 그래프]]<ref>{{하버드 인용 본문|Naor|Naor|Schaffer|1987}}.</ref> 및 경계 클릭 폭 그래프를 포함하여 더 넓은 종류의 그래프에 대한 채색 다항식을 계산하는 것으로 알려져 있다.<ref>{{하버드 인용 본문|Giménez|Hliněný|Noy|2005}}; {{하버드 인용 본문|Makowsky|Rotics|Averbouch|Godlin|2006}}.</ref> 후자의 종류에는 외부 평면 그래프와 같은 경계 트리 너비 의 여그래프 및 그래프가 포함된다.

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

: <math>\varphi^{n+m}=\left (\frac{1+\sqrt{5}}{2} \right)^{n+m}\in O\left(1.62^{n+m}\right),</math>

분석은 입력 그래프의 [[신장 부분 그래프|신장 부분]] 그래프의 수 <math>t(G)</math>의 다항식 인자 안으로 개선될 수 있다.<ref>{{하버드 인용 본문|Sekine|Imai|Tani|1995}}</ref> 실제로 일부 재귀 호출을 피하기 위해 [[분기 한정법|분기 및 경계]] 전략과 [[동형 사상|그래프 동형사상]] 거부가 사용되며, 실행 시간은 꼭지점 쌍을 선택하는 데 사용되는 경험적 방법에 따라 달라진다.

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

=== 계산 복잡도 ===
주어진 그래프의 3가지 색상 수를 계산하는 문제는 [[샤프-P|#P]] -완전 문제의 표준 예이므로 채색 다항식의 계수를 계산하는 문제는 #P-난해이다. 마찬가지로 주어진 ''G에'' 대해 <math>P(G, 3)</math>를 계산하는 것도 #P-완전이다. 반면에, <math>k=0,1,2</math>에 대해 <math>P(G, k)</math>를 계산하기는 쉽다. 그래서 해당 문제는 다항식 시간 계산이 가능하다. <math>k>3</math>인 정수의 경우 문제는 #P-난해이며, 이는<math>k=3</math>인 경우와 유사하게 확립되었다.  <math>P(G, x)</math>는 세 개의 "쉬운 점"을 제외한 모든 ''x''(음의 정수 및 모든 [[복소수]] 포함)에 대해 #P-난해이다.<ref>{{하버드 인용 본문|Jaeger|Vertigan|Welsh|1990}}, based on a reduction in {{하버드 인용|Linial|1986}}.</ref> 따라서 #P-난해의 관점에서 채색 다항식 계산의 복잡도가 완전히 이해된다.

전개

: <math>P(G, x)= a_1 x + a_2x^2+\cdots +a_nx^n</math>

에서 계수 <math>a_n</math>는 항상 1과 같고 계수의 다른 여러 속성이 알려져 있다. 이는 일부 계수를 계산하기 쉬운지에 대한 의문을 제기한다. 그러나 고정된 ''r ≥ 1'' 와 주어진 그래프 ''G''에 대해 ''a<sub>r</sub>'' 을 계산하는 계산 문제는 이분 평면 그래프의 경우에도 #P-난해이다.<ref>{{하버드 인용 본문|Oxley|Welsh|2002}}</ref>

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

== 각주 ==
{{각주}}

== 참고자료 ==
 {{참고 자료 시작|2}}
*{{인용|last=Biggs|first=N.|title=Algebraic Graph Theory|publisher=Cambridge University Press|year=1993|isbn=978-0-521-45897-9}}
*{{인용|last1=Chao|first1=C.-Y.|last2=Whitehead|first2=E. G.|contribution=On chromatic equivalence of graphs|title=Theory and Applications of Graphs|year=1978|volume=642|pages=121–131|publisher=Springer|series=Lecture Notes in Mathematics|isbn=978-3-540-08666-6}}
*{{인용|last1=Dong|first1=F. M.|last2=Koh|first2=K. M.|last3=Teo|first3=K. L.|title=Chromatic polynomials and chromaticity of graphs|publisher=World Scientific Publishing Company|year=2005|isbn=978-981-256-317-0}}
* {{인용|title=Structural Analysis of Complex Networks|chapter=Graph polynomials and their applications I: The Tutte polynomial|first1=Joanna A.|last1=Ellis-Monaghan|author1-link=Jo Ellis-Monaghan|first2=Criel|last2=Merino|arxiv=0803.3079|date=2011|isbn=978-0-8176-4789-6|editor-last=Dehmer|editor-first=Matthias|language=en-gb|doi=10.1007/978-0-8176-4789-6_9|s2cid=585250}}
*{{인용|last1=Giménez|first1=O.|last2=Hliněný|first2=P.|last3=Noy|first3=M.|contribution=Computing the Tutte polynomial on graphs of bounded clique-width|doi=10.1007/11604686_6|pages=59–68|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|title=Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005)|volume=3787|year=2005|isbn=978-3-540-31000-6|citeseerx=10.1.1.353.6385}}
*{{인용|last1=Goldberg|first1=L.A.|author1-link=Leslie Ann Goldberg|last2=Jerrum|first2=M.|author2-link=Mark Jerrum|title=Inapproximability of the Tutte polynomial|journal=Information and Computation|doi=10.1016/j.ic.2008.04.003|year=2008|volume=206|pages=908|issue=7|arxiv=cs/0605140|s2cid=53304001}}
*{{인용|last1=Helme-Guizon|first1=Laure|last2=Rong|first2=Yongwu|title=A categorification of the chromatic polynomial|journal=Algebraic & Geometric Topology|doi=10.2140/agt.2005.5.1365|year=2005|volume=5|pages=1365–1388|issue=4|arxiv=math/0412264|s2cid=1339633}}
*{{인용|last=Huh|first=June|arxiv=1008.4749|doi=10.1090/S0894-0347-2012-00731-0|issue=3|journal=Journal of the American Mathematical Society|mr=2904577|pages=907–927|title=Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs|volume=25|year=2012|s2cid=13523955}}
*{{인용|doi=10.1017/S0963548300000705|last1=Jackson|first1=B.|title=A Zero-Free Interval for Chromatic Polynomials of Graphs|journal=Combinatorics, Probability and Computing|volume=2|issue=3|pages=325–336|year=1993|s2cid=39978844}}
*{{인용|doi=10.1017/S0305004100068936|last1=Jaeger|first1=F.|last2=Vertigan|first2=D. L.|last3=Welsh|first3=D. J. A.|title=On the computational complexity of the Jones and Tutte polynomials|journal=Mathematical Proceedings of the Cambridge Philosophical Society|volume=108|issue=1|pages=35–53|year=1990|bibcode=1990MPCPS.108...35J|s2cid=121454726}}
*{{인용|doi=10.1137/0607036|last=Linial|first=N.|authorlink=Nati Linial|title=Hard enumeration problems in geometry and combinatorics|journal=SIAM J. Algebr. Discrete Methods|volume=7|issue=2|pages=331–335|year=1986}}
*{{인용|last1=Makowsky|first1=J. A.|last2=Rotics|first2=U.|last3=Averbouch|first3=I.|last4=Godlin|first4=B.|contribution=Computing graph polynomials on graphs of bounded clique-width|doi=10.1007/11917496_18|pages=191–204|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|title=Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006)|volume=4271|year=2006|isbn=978-3-540-48381-6|citeseerx=10.1.1.76.2320}}
*{{인용|last1=Naor|first1=J.|last2=Naor|first2=M.|last3=Schaffer|first3=A.|contribution=Fast parallel algorithms for chordal graphs|doi=10.1145/28395.28433|pages=355–364|title=Proc. 19th ACM Symp. Theory of Computing (STOC '87)|year=1987|isbn=978-0897912211|s2cid=12132229|doi-access=free}}.
*{{인용|last1=Oxley|first1=J. G.|last2=Welsh|first2=D. J. A.|title=Chromatic, flow and reliability polynomials: The complexity of their coefficients.|journal=[[Combinatorics, Probability and Computing]]|volume=11|year=2002|issue=4|pages=403–426|doi=10.1017/S0963548302005175|s2cid=14918970}}
*{{인용|last1=Pemmaraju|first1=S.|last2=Skiena|first2=S.|title=Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica|publisher=Cambridge University Press|year=2003|at=section 7.4.2|isbn=978-0-521-80686-2}}
*{{인용|last=Read|first=R. C.|author-link=Ronald C. Read|title=An introduction to chromatic polynomials|journal=[[Journal of Combinatorial Theory]]|year=1968|pages=52–71|volume=4|doi=10.1016/S0021-9800(68)80087-0|url=http://dml.cz/bitstream/handle/10338.dmlcz/128421/CzechMathJ_43-1993-3_10.pdf|doi-access=free}}
*{{인용|last1=Sekine|first1=Kyoko|last2=Imai|first2=Hiroshi|last3=Tani|first3=Seiichiro|editor1-last=Staples|editor1-first=John|editor2-last=Eades|editor2-first=Peter|editor3-last=Katoh|editor3-first=Naoki|editor4-last=Moffat|editor4-first=Alistair|contribution=Computing the Tutte polynomial of a graph of moderate size|doi=10.1007/BFb0015427|pages=224–233|publisher=Springer|series=Lecture Notes in Computer Science|title=Algorithms and Computation, 6th International Symposium, ISAAC '95, Cairns, Australia, December 4–6, 1995, Proceedings|volume=1004|year=1995|isbn=978-3-540-60573-7}}
*{{인용|doi=10.1017/S0963548303006023|last=Sokal|first=A. D.|author-link=Alan Sokal|title=Chromatic Roots are Dense in the Whole Complex Plane|journal=[[Combinatorics, Probability and Computing]]|year=2004|pages=221–261|volume=13|issue=2|arxiv=cond-mat/0012369|s2cid=5549332}}
*{{인용|doi=10.1016/0012-365X(73)90108-8|last=Stanley|first=R. P.|title=Acyclic orientations of graphs|journal=[[Discrete Mathematics (journal)|Discrete Math.]]|volume=5|pages=171–178|year=1973|issue=2|url=http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf}}
*{{인용|last=Voloshin|first=Vitaly I.|title=Coloring Mixed Hypergraphs: Theory, Algorithms and Applications.|publisher=American Mathematical Society|year=2002|isbn=978-0-8218-2812-0}}
*{{인용|last=Wilf|first=H. S.|author-link=Herbert Wilf|title=Algorithms and Complexity|publisher=Prentice–Hall|year=1986|isbn=978-0-13-021973-2}}
{{참고 자료 끝}}

== 외부 링크 ==
* {{매스월드|제목=Chromatic polynomial}}
* [[플래닛매스|PlanetMath]] [http://planetmath.org/encyclopedia/ChromaticPolynomial.html Chromatic polynomial] {{웹아카이브|url=https://web.archive.org/web/20080820122306/http://planetmath.org/encyclopedia/ChromaticPolynomial.html|date=2008-08-20}}
* Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [https://archive.today/20121220104146/http://www.ecs.vuw.ac.nz/~djp/tutte/]

[[분류:그래프 색칠]]