क्रोमैटिक बहुपद

3 शीर्षों पर सभी गैर-समरूपी रेखांकन और उनके रंगीन बहुपद, शीर्ष से दक्षिणावर्त। स्वतंत्र 3-सेट: k³. एक किनारा और एक शीर्ष: k²(k – 1). 3-पथ: k(k – 1)². 3-क्लिक: k(k – 1)(k – 2).

रंगीन बहुपद बीजगणितीय ग्राफ सिद्धांत, गणित की एक शाखा में अध्ययन किया गया ग्राफ बहुपद है। यह रंगों की संख्या के फलन के रूप में ग्राफ रंगों की संख्या की गणना करता है और मूल रूप से चार रंगों की समस्या का अध्ययन करने के लिए जॉर्ज डेविड बिरखॉफ द्वारा परिभाषित किया गया था। यह हस्लर व्हिटनी और डब्ल्यू टी टुट्टे द्वारा टट्टे बहुपद के लिए सामान्यीकृत किया गया था, इसे सांख्यिकीय भौतिकी के पॉट्स मॉडल से जोड़ा गया था।

इतिहास

चार रंग प्रमेय को साबित करने के प्रयास में, जॉर्ज डेविड बिरखॉफ़ ने 1912 में रंगीन बहुपद का प्रारम्भ किया, इसे केवल समतल रेखांकन के लिए परिभाषित किया गया था। अगर $P(G,k)$ k रंगों के साथ G के उचित रंगों की संख्या को दर्शाता है तो चार रंग प्रमेय को $P(G,4)>0$ सभी समतल रेखांकन के लिए G दिखाकर स्थापित किया जा सकता है। इस तरह उन्होंने गणितीय विश्लेषण और सार बीजगणित के शक्तिशाली उपकरणों को बहुपदों की जड़ों का अध्ययन करने के लिए मिश्रित रंग की समस्या को लागू करने की आशा की थी।

हस्लर व्हिटनी ने 1932 में समतल मामले से सामान्य ग्राफ़ के लिए बिरखॉफ़ के बहुपद को सामान्यीकृत किया। 1968 में, रोनाल्ड सी. रीड ने पूछा कि कौन से बहुपद कुछ ग्राफ़ के रंगीन बहुपद हैं, एक प्रश्न जो खुला रहता है, और वर्णक्रमीय समकक्ष ग्राफ़ की अवधारणा पेश की। आज, रंगीन बहुपद बीजगणितीय ग्राफ सिद्धांत के केंद्रीय विषय में से एक हैं।

परिभाषा

के रंगों का उपयोग करते हुए 3 शीर्षों के साथ वर्टेक्स ग्राफ के सभी उचित शीर्ष रंग $k=0,1,2,3$. प्रत्येक ग्राफ का रंगीन बहुपद उचित रंगों की संख्या के माध्यम से प्रक्षेपित होता है।

ग्राफ G के लिए, $P(G,k)$ इसके (उचित) शीर्ष k-रंगों की संख्या की गणना करता है।

अन्य सामान्यतः इस्तेमाल किए जाने वाले नोटेशन में सम्मलित हैं $P_{G}(k)$, $\chi _{G}(k)$, या $\pi _{G}(k)$. एक अद्वितीय बहुपद है $P(G,x)$ जिसका मूल्यांकन किसी भी पूर्णांक k ≥ 0 पर किया जाता है $P(G,k)$; इसे G का रंगीन बहुपद कहते हैं।

उदाहरण के लिए, पथ ग्राफ को रंगने के लिए $P_{3}$ k रंगों के साथ 3 शीर्षों पर, कोई भी पहले शीर्ष के लिए k रंगों में से कोई भी चुन सकता है, इनमें से कोई भी $k-1$ दूसरे शीर्ष के लिए शेष रंग, और अंत में तीसरे शीर्ष के लिए, इनमें से कोई भी $k-1$ रंग जो दूसरे शीर्ष की पसंद से भिन्न हैं। इसलिए, $P(P_{3},k)=k\cdot (k-1)\cdot (k-1)$ k - रंगों की संख्या है $P_{3}$. एक चर x (आवश्यक रूप से पूर्णांक नहीं) के लिए, हमारे पास इस प्रकार है $P(P_{3},x)=x(x-1)^{2}=x^{3}-2x^{2}+x$. (रंग जो केवल रंगों की अनुमति या G के ग्राफ ऑटोमोर्फिज्म द्वारा भिन्न होते हैं, उन्हें अभी भी भिन्न के रूप में गिना जाता है।)

विलोपन–संकुचन

Main article: विलोपन-संकुचन सूत्र

तथ्य यह है कि 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$, या समान रंग। पहले मामले में यह एक (उचित) k -रंग देता है $G+uv$, जबकि दूसरे मामले में यह रंग देता है $G/uv$. इसके विपरीत, G के प्रत्येक k -रंग को विशिष्ट रूप से k -रंग से प्राप्त किया जा सकता है $G+uv$ या $G/uv$ (अगर $u$ और $v$ G में आसन्न नहीं हैं)।

इसलिए रंगीन बहुपद को पुनरावर्ती रूप से परिभाषित किया जा सकता है

$P(G,x)=x^{n}$ n शीर्षों पर कोर रहित ग्राफ़ के लिए, और

$P(G,x)=P(G-uv,x)-P(G/uv,x)$ कोर वाले ग्राफ G के लिए $uv$ ( अक्रमतः से चुना गया है )।

चूंकि एजलेस ग्राफ के k -रंगों की संख्या वास्तव में है $k^{n}$, यह कोरो की संख्या पर प्रेरण द्वारा अनुसरण करता है जो सभी G के लिए बहुपद है $P(G,x)$ प्रत्येक पूर्णांक बिंदु x = k पर k -रंगों की संख्या के साथ मेल खाता है। विशेष रूप से, रंगीन बहुपद अंक के माध्यम से अधिकतम n पर डिग्री का अद्वितीय प्रक्षेपित बहुपद है

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

टुट्टे की जिज्ञासा जिसके बारे में अन्य ग्राफ अपरिवर्तनीय ने इस तरह की पुनरावृत्ति के समाधान के लिए, उन्हें रंगीन बहुपद, टुट्टे बहुपद के द्विभाजित सामान्यीकरण की खोज $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 की रंगीनता के बारे में कम से कम उतनी ही जानकारी सम्मलित होती है जितनी रंगीन संख्या होती है। दरअसल, रंगीन संख्या सबसे छोटी धनात्मक पूर्णांक है जो रंगीन बहुपद का शून्य नहीं है,

$\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)$ इंगित करने तक है।

यदि G में n शीर्ष और c जुड़ा हुआ घटक है (ग्राफ़ सिद्धांत) $G_{1},\ldots ,G_{c}$, तब

• $x^{0},\ldots ,x^{c-1}$ के गुणांक शून्य हैं।
• $x^{c},\ldots ,x^{n}$ के गुणांक सभी गैर-शून्य हैं और संकेतों में वैकल्पिक हैं।
• $x^{n}$ 1 का गुणांक है ( बहुपद मोनिक है )।
• $x^{n-1}$ का गुणांक $-|E(G)|$ है।

हम साधारण ग्राफ G पर कोरो की संख्या पर प्रेरण के माध्यम से इसे $n$ शिखर और $k$ कोरो साबित करते हैं। जब कि $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$ केवल कोर e को हटाकर G से $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_{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}.$

रंगीन तुल्यता

The three graphs with a chromatic polynomial equal to $(x-2)(x-1)^{3}x$.

दो ग्राफ़ों को वर्णिक रूप से समतुल्य कहा जाता है यदि उनके पास एक ही रंगीन बहुपद है। आइसोमॉर्फिक ग्राफ़ में समान रंगीन बहुपद होते हैं, लेकिन गैर-आइसोमॉर्फिक ग्राफ़ क्रोमेटिक रूप से समतुल्य हो सकते हैं। उदाहरण के लिए, n शीर्षों पर स्थित सभी वृक्षों में एक ही वर्णिक बहुपद होता है।

विशेष रूप से, $(x-1)^{3}x$ दोनों पंजे (ग्राफ सिद्धांत) और 4 कोने पर पथ ग्राफ का रंगीन बहुपद है।

एक ग्राफ क्रोमैटिक रूप से अद्वितीय होता है यदि यह समरूपता तक, इसके रंगीन बहुपद द्वारा निर्धारित किया जाता है। दूसरे शब्दों में, जी तब क्रोमेटिक रूप से अद्वितीय है $P(G,x)=P(H,x)$ इसका अर्थ यह होगा कि G और H तुल्याकारी हैं। सभी चक्र रेखांकन रंगीन अद्वितीय हैं।

रंगीन जड़ें

एक रंगीन बहुपद के फ़ंक्शन (या शून्य) की जड़, जिसे "क्रोमैटिक रूट" कहा जाता है, एक मान x है जहां $P(G,x)=0$. रंगीन जड़ों का बहुत अच्छी तरह से अध्ययन किया गया है, वास्तव में, रंगीन बहुपद को परिभाषित करने के लिए बिरखॉफ की मूल प्रेरणा यह दिखाने के लिए थी कि प्लानर ग्राफ के लिए, $P(G,x)>0$ x ≥ 4 के लिए। इससे चार रंगों की प्रमेय स्थापित हो जाती।

कोई भी ग्राफ 0-रंग का नहीं हो सकता, इसलिए 0 हमेशा एक रंगीन मूल होता है। केवल कोर रहित ग्राफ़ 1-रंग के हो सकते हैं, इसलिए 1 कम से कम एक कोर वाले प्रत्येक ग्राफ़ का एक रंगीन मूल है। दूसरी ओर, इन दो बिंदुओं को छोड़कर, किसी भी ग्राफ में 32/27 से कम या उसके बराबर वास्तविक संख्या में एक रंगीन जड़ नहीं हो सकती है। टुट्टे का एक परिणाम सुनहरा अनुपात को जोड़ता है $\phi$ रंगीन जड़ों के अध्ययन के साथ, यह दर्शाता है कि रंगीन जड़ें बहुत करीब मौजूद हैं $\phi ^{2}$: अगर $G_{n}$ तब एक गोले का समतलीय त्रिकोण है

$P(G_{n},\phi ^{2})\leq \phi ^{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}$ बहुपद के गुणांक हैं $P(G,x)$ आधार में $1,(x)_{1},(x)_{2},(x)_{3},\ldots$ गिरते फैक्टोरियल का।

होने देना $a_{k}$ का k-th गुणांक हो $P(G,x)$ मानक आधार पर $1,x,x^{2},x^{3},\ldots$, वह है:

$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}$.

वर्गीकरण

क्रोमैटिक बहुपद एक होमोलॉजी सिद्धांत द्वारा वर्गीकरण है जो खोवानोव होमोलॉजी से निकटता से संबंधित है।

एल्गोरिदम

Chromatic polynomial
Input	Graph G with n vertices.
Output	Coefficients of $P(G,x)$
Running time	$O(2^{n}n^{r})$ for some constant $r$
Complexity	#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$

रंगीन बहुपद से जुड़ी कम्प्यूटेशनल समस्याओं में सम्मलित हैं

• रंगीन बहुपद ढूँढना $P(G,x)$ किसी दिए गए ग्राफ G का;
• मूल्यांकन $P(G,x)$ दिए गए G के लिए एक निश्चित x पर।

पहली समस्या अधिक सामान्य है क्योंकि यदि हम के गुणांकों को जानते हैं $P(G,x)$ हम बहुपद समय में किसी भी बिंदु पर इसका मूल्यांकन कर सकते हैं क्योंकि डिग्री n है। दूसरे प्रकार की समस्या की कठिनाई x के मान पर दृढ़ता से निर्भर करती है और कम्प्यूटेशनल जटिलता सिद्धांत में इसका गहन अध्ययन किया गया है। जब x एक प्राकृतिक संख्या है, तो इस समस्या को सामान्य रूप से किसी दिए गए ग्राफ़ के x-रंगों की संख्या की गणना के रूप में देखा जाता है। उदाहरण के लिए, इसमें 3-रंगों की संख्या गिनने की समस्या '#3-रंग' सम्मलित है, गिनती की जटिलता के अध्ययन में एक विहित समस्या, गिनती वर्ग Sharp-P|#P के लिए पूर्ण।

कुशल एल्गोरिदम

कुछ बुनियादी ग्राफ वर्गों के लिए, रंगीन बहुपद के लिए बंद सूत्र ज्ञात हैं। उदाहरण के लिए, यह पेड़ों और गुटों के लिए सही है, जैसा कि ऊपर दी गई तालिका में सूचीबद्ध है।

बहुपद समय एल्गोरिदम व्यापक वर्गों के रेखांकन के लिए रंगीन बहुपद की गणना के लिए जाना जाता है, जिसमें कॉर्डल ग्राफ भी सम्मलित हैं। और घिरे गुट-चौड़ाई के रेखांकन। बाद वाले वर्ग में बाउंडेड ट्री-चौड़ाई के कोग्राफ और ग्राफ़ सम्मलित हैं, जैसे कि आउटरप्लानर ग्राफ़।

विलोपन–संकुचन

विलोपन-संकुचन पुनरावृत्ति रंगीन बहुपद की गणना करने का एक तरीका देता है, जिसे विलोपन-संकुचन एल्गोरिथम कहा जाता है। पहले रूप में (ऋण के साथ), पुनरावृत्ति खाली ग्राफ के संग्रह में समाप्त हो जाती है। दूसरे रूप में (प्लस के साथ), यह पूर्ण ग्राफ़ के संग्रह में समाप्त होता है। यह ग्राफ कलरिंग के लिए कई एल्गोरिदम का आधार बनता है। कंप्यूटर बीजगणित प्रणाली के कॉम्बिनेटरिका पैकेज में क्रोमैटिकपोलिनोमियल फ़ंक्शन मेथेमेटिका दूसरी पुनरावृत्ति का उपयोग करता है यदि ग्राफ सघन है, और पहली पुनरावृत्ति यदि ग्राफ विरल है। किसी भी फॉर्मूले का सबसे खराब स्थिति चलने का समय फाइबोनैचि संख्याओं के समान पुनरावृत्ति संबंध को संतुष्ट करता है, इसलिए सबसे खराब स्थिति में, एल्गोरिथ्म एक बहुपद कारक के भीतर समय पर चलता है

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

n शीर्षों और m कोरो वाले ग्राफ़ पर। संख्या के एक बहुपद कारक के भीतर विश्लेषण में सुधार किया जा सकता है $t(G)$ इनपुट ग्राफ के फैले हुए पेड़ (गणित) का। अभ्यास में, कुछ पुनरावर्ती कॉलों से बचने के लिए शाखा और बाध्य रणनीतियों और समरूपता अस्वीकृति को नियोजित किया जाता है, चलने का समय वर्टेक्स जोड़ी को चुनने के लिए उपयोग किए जाने वाले हेयुरिस्टिक पर निर्भर करता है।

घन विधि

ग्राफ़ रंगों पर एक प्राकृतिक ज्यामितीय परिप्रेक्ष्य है, यह देखते हुए कि प्रत्येक शीर्ष पर प्राकृतिक संख्याओं के असाइनमेंट के रूप में, एक ग्राफ़ रंग पूर्णांक जाली में एक वेक्टर है। चूंकि दो शिखर हैं $i$ और $j$ एक ही रंग दिया जा रहा है के बराबर है $i$वें और $j$कलरिंग वेक्टर में वां कोऑर्डिनेट बराबर होने पर, प्रत्येक कोर को फॉर्म के हाइपरप्लेन से जोड़ा जा सकता है $\{x\in R^{d}:x_{i}=x_{j}\}$. किसी दिए गए ग्राफ़ के लिए ऐसे हाइपरप्लेन का संग्रह हाइपरप्लेन की ग्राफिक व्यवस्था कहलाता है। ग्राफ के उचित रंग वे जाली बिंदु हैं जो वर्जित हाइपरप्लेन से बचते हैं। के एक सेट तक सीमित करना $k$ रंग, जाली बिंदु घन में समाहित हैं $[0,k]^{n}$. इस संदर्भ में रंगीन बहुपद जाली बिंदुओं की संख्या की गणना करता है $[0,k]$-क्यूब जो ग्राफिक व्यवस्था से बचते हैं।

कम्प्यूटेशनल जटिलता

किसी दिए गए ग्राफ के 3-रंगों की संख्या की गणना करने की समस्या तीव्र-पी|#पी-पूर्ण समस्या का एक विहित उदाहरण है, इसलिए रंगीन बहुपद के गुणांकों की गणना करने की समस्या #पी-हार्ड है। इसी प्रकार मूल्यांकन करना $P(G,3)$ दिए गए G के लिए #P-पूर्ण है। दूसरी ओर, के लिए $k=0,1,2$ गणना करना आसान है $P(G,k)$, इसलिए संबंधित समस्याएँ बहुपद-समय संगणनीय हैं। पूर्णांकों के लिए $k>3$ समस्या #पी-हार्ड है, जो केस के समान स्थापित है $k=3$. दरअसल, यह पता चला है $P(G,x)$ तीन "आसान बिंदुओं" को छोड़कर सभी x (ऋणात्मक पूर्णांक और यहां तक ​​कि सभी जटिल संख्याओं सहित) के लिए #P-हार्ड है। इस प्रकार, #पी-कठोरता के दृष्टिकोण से, रंगीन बहुपद की गणना की जटिलता को पूरी तरह से समझा जाता है।

विस्तार में

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

गुणांक $a_{n}$ हमेशा 1 के बराबर होता है, और गुणांक के कई अन्य गुण ज्ञात होते हैं। यह सवाल उठाता है कि क्या कुछ गुणांकों की गणना करना आसान है। हालाँकि कंप्यूटिंग की कम्प्यूटेशनल समस्या a_rएक निश्चित आर ≥ 1 के लिए और एक दिया गया ग्राफ जी #पी-हार्ड है, द्विपक्षीय प्लानर ग्राफ के लिए भी। कंप्यूटिंग के लिए कोई सन्निकटन एल्गोरिदम नहीं $P(G,x)$ तीन आसान बिंदुओं को छोड़कर किसी भी x के लिए जाने जाते हैं। पूर्णांक बिंदुओं पर $k=3,4,\ldots$, किसी दिए गए ग्राफ़ को के-रंगीन किया जा सकता है या नहीं, यह तय करने की संबंधित निर्णय समस्या एनपी कठिन है। इस तरह की समस्याओं को किसी बाउंडेड-एरर प्रोबेबिलिस्टिक एल्गोरिथम द्वारा किसी भी गुणक कारक के लिए अनुमानित नहीं किया जा सकता है जब तक कि एनपी = आरपी, क्योंकि कोई भी गुणक सन्निकटन 0 और 1 के मानों को अलग कर देगा, प्रभावी रूप से बाउंड-एरर प्रोबेबिलिस्टिक पॉलीनोमियल टाइम में निर्णय संस्करण को हल करेगा। विशेष रूप से, इसी धारणा के तहत, यह FPRAS | पूर्ण बहुपद समय यादृच्छिक सन्निकटन योजना (FPRAS) की संभावना को बाहर करता है। अन्य बिंदुओं के लिए, अधिक जटिल तर्कों की आवश्यकता है, और प्रश्न सक्रिय शोध का फोकस है। As of 2008, यह ज्ञात है कि कंप्यूटिंग के लिए कोई FPRAS नहीं है $P(G,x)$ किसी भी x > 2 के लिए, जब तक कि एनपी (जटिलता वर्ग)  =  आरपी (जटिलता वर्ग) न हो।

संदर्भ

• 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, vol. 642, Springer, pp. 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", in Dehmer, Matthias (ed.), Structural Analysis of Complex Networks (in British English), 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, 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, vol. 4271, Springer-Verlag, pp. 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), pp. 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", in Staples, John; Eades, Peter; Katoh, Naoki; Moffat, Alistair (eds.), Algorithms and Computation, 6th International Symposium, ISAAC '95, Cairns, Australia, December 4–6, 1995, Proceedings, Lecture Notes in Computer Science, vol. 1004, Springer, pp. 224–233, doi:10.1007/BFb0015427
• 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 W., "Chromatic polynomial", MathWorld
• PlanetMath Chromatic polynomial
• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [1]