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

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 एक k -क्लिक-योग है $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 समरूपी हैं। सभी चक्र रेखांकन क्रोमैटिकअद्वितीय हैं।

क्रोमैटिक मूल

क्रोमैटिक बहुपद के फलन (या शून्य) की मूल, जिसे "क्रोमैटिकमूल" कहा जाता है, एक मान 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 -वॉ गुणांक हो $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
इनपुट	ग्राफ G को n शीर्षों के साथ।
उत्पादन	गुणांक के $P(G,x)$
कार्यकारी समय	$O(2^{n}n^{r})$ कुछ स्थिर के लिए $r$
जटिलता	#P-hard
कमी से	#3SAT

#k-रंग
इनपुट	ग्राफ G को n शीर्षों के साथ।
उत्पादन	$P(G,k)$
कार्यकारी समय	In P के लिए $k=0,1,2$. $O(1.6262^{n})$ के लिए $k=3$. अन्यथा $O(2^{n}n^{r})$कुछ स्थिर के लिए $r$
जटिलता	#P-कठिन जब तक $k=0,1,2$
सन्निकटन	No FPRAS for $k>2$

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

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

पहली समस्या अधिक सामान्य है क्योंकि यदि हम के गुणांकों को जानते हैं $P(G,x)$ हम बहुपद समय में किसी भी बिंदु पर इसका मूल्यांकन कर सकते हैं क्योंकि डिग्री n है। दूसरे प्रकार की समस्या की कठिनाई x के मान पर दृढ़ता से निर्भर करती है और कम्प्यूटेशनल जटिलता सिद्धांत में इसका गहन अध्ययन किया गया है। जब x एक प्राकृतिक संख्या है, तो इस समस्या को सामान्य रूप से किसी दिए गए रेखांकन के x -रंगों की संख्या की गणना के रूप में देखा जाता है। उदाहरण के लिए, इसमें 3-रंगों की संख्या गिनने की समस्या '#3-रंग' सम्मिलित है, गिनती की जटिलता के अध्ययन में विहित समस्या, गणना वर्ग #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 -पूर्ण समस्या का विहित उदाहरण है, इसलिए क्रोमैटिक बहुपद के गुणांकों की गणना करने की समस्या #P -कठिन है। इसी प्रकार मूल्यांकन करना $P(G,3)$ दिए गए G के लिए #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 के बराबर होता है, और गुणांक के कई अन्य गुण ज्ञात होते हैं। यह सवाल उठाता है कि क्या कुछ गुणांकों की गणना करना आसान है। यधपि कंप्यूटिंग की कम्प्यूटेशनल समस्या a_r एक निश्चित r ≥ 1 के लिए और एक दिया गया ग्राफ G #P-कठिन है, द्विपक्षीय प्लानर ग्राफ के लिए भी है।

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

संदर्भ

• 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]