ग्राफ कलरिंग

3 रंगों के साथ पीटरसन ग्राफ का उचित शीर्ष रंग, न्यूनतम संभव संख्या।

ग्राफ़ सिद्धांत में, ग्राफ़ कलरिंग ग्राफ लेबलिंग का एक विशेष स्थिति है; यह कुछ बाधाओं के अधीन एक ग्राफ के तत्वों के लिए पारंपरिक रूप से "रंग" कहे जाने वाले लेबल का एक असाइनमेंट है। अपने सरलतम रूप में, यह ग्राफ के शीर्षों को इस प्रकार रंगने का एक तरीका है कि कोई भी दो आसन्न शीर्ष एक ही रंग के न हों; इसे वर्टेक्स कलरिंग कहा जाता है। इसी तरह, किनारे का रंग प्रत्येक किनारे को एक रंग प्रदान करता है ताकि कोई भी दो आसन्न किनारे एक ही रंग के न हों, और समतल ग्राफ का एक चेहरा रंग प्रत्येक चेहरे या क्षेत्र को एक रंग प्रदान करता है ताकि कोई भी दो आसन्न किनारे एक ही रंग के चेहरे न हों एक ही रंग का न हो।

वर्टेक्स कलरिंग का उपयोग प्रायः ग्राफ कलरिंग की समस्याओं को पेश करने के लिए किया जाता है, क्योंकि अन्य कलरिंग समस्याओं को वर्टेक्स कलरिंग इंस्टेंस में बदला जा सकता है। उदाहरण के लिए, एक ग्राफ़ का एक किनारा रंग उसके लाइन ग्राफ़ का सिर्फ एक शीर्ष रंग है, और एक समतल ग्राफ़ का एक चेहरा रंग उसके दोहरे का सिर्फ एक शीर्ष रंग है। हालांकि, गैर-शीर्ष रंग की समस्याओं को प्रायः कहा जाता है और उनका अध्ययन किया जाता है। यह आंशिक रूप से शैक्षणिक है, और आंशिक रूप से क्योंकि कुछ समस्याओं का उनके गैर-शीर्ष रूप में सबसे अच्छा अध्ययन किया जाता है, जैसा कि किनारे के रंग के स्थिति में है।

रंगों का उपयोग करने की परिपाटी एक मानचित्र के देशों को रंगने से उत्पन्न होती है, जहाँ प्रत्येक चेहरा सचमुच रंगीन होता है। यह सतह में अंतर्निहितग्राफ के चेहरों को रंगने के लिए सामान्यीकृत किया गया था। प्लेनर द्वैत द्वारा यह कोने को रंगने लगा, और इस रूप में यह सभी रेखांकन के लिए सामान्य हो गया। गणितीय और कंप्यूटर अभ्यावेदन में, पहले कुछ धनात्मक या गैर-ऋणात्मक पूर्णांकों को "रंग" के रूप में उपयोग करना विशिष्ट है। सामान्य तौर पर, कोई भी परिमित सेट को "रंग सेट" के रूप में उपयोग कर सकता है। रंजक समस्या की प्रकृति रंगों की संख्या पर निर्भर करती है न कि वे क्या हैं।

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

नोट: इस लेख में प्रयुक्त कई शब्दों को राफ सिद्धांत की शब्दावली में परिभाषित किया गया है।

इतिहास

See also: चार रंग प्रमेय का इतिहास and ग्राफ सिद्धांत का इतिहास

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

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

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

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

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

परिभाषा और शब्दावली

यह ग्राफ 12 अलग-अलग तरीकों से 3 रंगों का हो सकता है।

वर्टेक्स रंग

जब बिना किसी योग्यता के उपयोग किया जाता है, तो ग्राफ़ का रंग लगभग हमेशा एक उचित शीर्ष रंग होता है, अर्थात् ग्राफ़ के शीर्षों को रंगों के साथ लेबल करना, जैसे कि एक ही किनारे (ग्राफ़ सिद्धांत) को साझा करने वाले दो शीर्षों का रंग समान नहीं होता है। चूंकि एक पाश (ग्राफ सिद्धांत) (अर्थात् सीधे अपने आप में एक कनेक्शन) के साथ एक शीर्ष कभी भी ठीक से रंगीन नहीं हो सकता है, यह समझा जाता है कि इस संदर्भ में ग्राफ लूपलेस हैं।

वर्टेक्स लेबल्स के लिए रंगों का उपयोग करने की शब्दावली मैप कलरिंग पर वापस जाती है। लाल और नीला जैसे लेबल केवल तभी उपयोग किए जाते हैं जब रंगों की संख्या कम होती है, और सामान्यतः यह समझा जाता है कि लेबल पूर्णांक से खींचे गए हैं {1, 2, 3, …}. अधिक से अधिक उपयोग करने वाला रंग k रंग कहा जाता है (उचित) k-रंग। किसी ग्राफ़ को रंगने के लिए आवश्यक रंगों की न्यूनतम संख्या G इसकी रंगीन संख्या कहा जाता है, और इसे प्रायः निरूपित किया जाता है χ(G). कभी-कभी γ(G) उपयोग किया जाता है, क्योंकि χ(G) ग्राफ की यूलर विशेषता को निरूपित करने के लिए भी प्रयोग किया जाता है। एक ग्राफ जिसे असाइन किया जा सकता है (उचित) k-रंग है k-रंगीन, और यह हैk-क्रोमैटिक अगर इसकी क्रोमैटिक संख्या बिल्कुल है k. एक ही रंग को सौंपे गए शीर्षों के एक उपसमुच्चय को रंग वर्ग कहा जाता है, ऐसा प्रत्येक वर्ग एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) बनाता है। इस प्रकार, एक k-coloring एक शीर्ष सेट को k-स्वतंत्र सेटों में विभाजित करने के बराबर है, और k-match और k-colourable शब्दों का अर्थ समान है।

रंगीन बहुपद

3 शीर्षों पर सभी गैर-समरूपी रेखांकन और उनके रंगीन बहुपद। खाली ग्राफ E₃ (लाल) 1-रंग स्वीकार करता है; पूरा ग्राफ K₃ (नीला) 3-रंगों को स्वीकार करता है; अन्य रेखांकन एक 2-रंग स्वीकार करते हैं।

Main article: रंगीन बहुपद

रंगीन बहुपद उन तरीकों की गणना करता है जिनमें कुछ दिए गए रंगों का उपयोग करके ग्राफ को रंगीन किया जा सकता है। उदाहरण के लिए, तीन रंगों का उपयोग करके, आसन्न छवि में ग्राफ़ को 12 तरीकों से रंगा जा सकता है। इसे केवल दो रंगों से नहीं रंगा जा सकता। चार रंगों से, इसे 24 + 4⋅12 = 72 तरीकों से रंगा जा सकता है: चारों रंगों का उपयोग करके, 4! = 24 वैध रंग (प्रत्येक चार रंगों का कोई भी 4-वर्टेक्स ग्राफ एक वैध रंग है); और चार में से तीन रंगों की हर पसंद के लिए, 12 मान्य 3-रंग हैं। इसलिए, उदाहरण में ग्राफ़ के लिए, मान्य रंगों की संख्या की तालिका इस तरह प्रारम्भ होगी:

उपलब्ध रंग	1	2	3	4	…
रंगों की संख्या	0	0	12	72	…

रंगीन बहुपद एक कार्य है P(G,t) जो की संख्या की गणना करता है t- का रंग G. जैसा कि नाम इंगित करता है, दिए गए के लिए G फंक्शन वास्तव में एक बहुपद है t. उदाहरण ग्राफ के लिए, P(G,t) = t(t – 1)²(t – 2), वास्तव में P(G,4) = 72.

रंगीन बहुपद में की रंगीनता के बारे में अधिक जानकारी सम्मिलित है G रंगीन संख्या की तुलना में। वास्तव में, χ सबसे छोटा धनात्मक पूर्णांक है जो χ(G) = min{k : P(G,k) > 0}.रंगीन बहुपद का शून्य नहीं है

कुछ रेखांकन के लिए रंगीन बहुपद

त्रिकोण K3	t(t – 1)(t – 2)
पूरा ग्राफ Kn	t(t – 1)(t – 2) … (t – (n – 1))
n शीर्षों वाला ट्री	t(t – 1)n – 1
चक्र Cn	(t – 1)n + (-1)n(t – 1)
पीटरसन ग्राफ	t(t – 1)(t – 2)(t7 – 12t6 + 67t5 – 230t4 + 529t3 – 814t2 + 775t – 352)

किनारे का रंग

Main article: किनारे का रंग

एक ग्राफ़ का एक किनारा रंग किनारों का एक उचित रंग है, जिसका अर्थ है कि किनारों को रंगों का एक असाइनमेंट ताकि एक ही रंग के दो किनारों पर कोई शीर्ष घटना न हो। एक किनारे का रंग k रंगों को कहा जाता है k-एज-कलरिंग और एज सेट को विभाजित करने की समस्या के बराबर है k मिलान (ग्राफ सिद्धांत)। किसी ग्राफ़ के किनारों को रंगने के लिए आवश्यक रंगों की सबसे छोटी संख्या G क्रोमैटिक सूचकांक या एज क्रोमैटिक नंबर है, χ′(G). टैट कलरिंग क्यूबिक ग्राफ का 3-किनारे वाला कलरिंग है। चार रंग प्रमेय इस दावे के बराबर है कि प्रत्येक प्लानर क्यूबिक पुल (ग्राफ सिद्धांत) ग्राफ एक टैट रंग को स्वीकार करता है।

कुल रंग

Main article: समग्र रंगाई

टोटल कलरिंग ग्राफ के कोने और किनारों पर कलरिंग का एक प्रकार है। जब किसी योग्यता के बिना उपयोग किया जाता है, तो कुल रंग हमेशा इस अर्थ में उचित माना जाता है कि कोई आसन्न कोने, कोई आसन्न किनारे नहीं, और कोई किनारा नहीं है और इसके अंत-कोने को एक ही रंग दिया जाता है। कुल रंगीन संख्या χ″(G) एक ग्राफ का G के कुल रंग में सबसे कम आवश्यक रंग G है।

बिना लेबल वाला रंग

किसी ग्राफ़ का लेबल रहित रंग ग्राफ़ के ग्राफ ऑटोमोर्फिज्म की क्रिया के अंतर्गत किसी रंग की समूह क्रिया (गणित) है। ध्यान दें कि रंग लेबल रहते हैं; यह वह ग्राफ है जिसे लेबल नहीं किया गया है। रंगीन बहुपद का एक एनालॉग है जो किसी दिए गए परिमित रंग सेट से ग्राफ के बिना लेबल वाले रंगों की संख्या की गणना करता है। अगर हम एक ग्राफ के रंग की व्याख्या करते हैं d में एक वेक्टर के रूप में शिखर $\mathbb {Z} ^{d}$, ऑटोमोर्फिज्म की क्रिया रंगीन वेक्टर में गुणांकों का क्रम परिवर्तन है।

गुण

वर्णक्रमीय संख्या पर ऊपरी सीमा

अलग-अलग रंगों को अलग-अलग रंगों में निर्दिष्ट करने से हमेशा एक उचित रंग मिलता है, इसलिए

$1\leq \chi (G)\leq n.$

एकमात्र ग्राफ़ जो 1-रंग का हो सकता है, वे किनारा रहित ग्राफ हैं। एक पूरा ग्राफ $K_{n}$ n शीर्षों की आवश्यकता है $\chi (K_{n})=n$ रंग की। एक इष्टतम रंग में रंग वर्गों की प्रत्येक जोड़ी के बीच ग्राफ के m किनारों में से कम से कम एक होना चाहिए, इसलिए

$\chi (G)(\chi (G)-1)\leq 2m.$

यदि G में आकार k का एक समूह (ग्राफ़ सिद्धांत) है, तो उस समूह को रंगने के लिए कम से कम k रंगों की आवश्यकता होती है; दूसरे शब्दों में, रंगीन संख्या कम से कम क्लिक संख्या है:

$\chi (G)\geq \omega (G).$

सही रेखांकन के लिए यह सीमा तंग है। क्लिक्स ढूँढना क्लिक्स समस्या के रूप में जाना जाता है।

अधिक सामान्यतः एक परिवार ${\mathcal {F}}$ रेखांकन का Χ-बाध्य है$\chi$-बाउंडेड अगर कोई फंक्शन है $c$ जैसे कि रेखांकन $G$ में ${\mathcal {F}}$ ज्यादा से ज्यादा रंगा जा सकता है $c(\omega (G))$ रंग, सही रेखांकन $c(\omega (G))=\omega (G)$के परिवार के लिए यह कार्य है .

2-रंगीन ग्राफ़ वास्तव में द्विदलीय ग्राफ़ हैं, जिनमें वृक्ष (ग्राफ़ सिद्धांत) और वन सम्मिलित हैं।

चार रंग प्रमेय के अनुसार, प्रत्येक प्लानर ग्राफ 4-रंगों का हो सकता है।

एक लोभी रंग दिखाता है कि प्रत्येक ग्राफ को अधिकतम शीर्ष डिग्री (ग्राफ सिद्धांत) की तुलना में एक और रंग से रंगा जा सकता है।

$\chi (G)\leq \Delta (G)+1.$

पूरा रेखांकन है $\chi (G)=n$ और $\Delta (G)=n-1$, और विषम चक्र हैं $\chi (G)=3$ और $\Delta (G)=2$, इसलिए इन ग्राफ़ के लिए यह बाउंड सर्वोत्तम संभव है। अन्य सभी मामलों में, सीमा में थोड़ा सुधार किया जा सकता है; ब्रूक्स प्रमेय बताता है

ब्रूक्स प्रमेय:$\chi (G)\leq \Delta (G)$ एक जुड़े हुए, सरल ग्राफ़ G के लिए, जब तक कि G एक पूर्ण ग्राफ़ या विषम चक्र न हो।

वर्णक्रमीय संख्या पर निचली सीमा

पिछले कुछ वर्षों में रंगीन सीमाओं के लिए कई निचली सीमाएं खोजी गई हैं:

हॉफमैन की बाउंड: चलो $W$ एक वास्तविक सममित मैट्रिक्स हो जैसे कि $W_{i,j}=0$ जब कभी भी $(i,j)$ में बढ़त नहीं है $G$. परिभाषित करना $\chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}$, कहाँ $\lambda _{\max }(W),\lambda _{\min }(W)$ के सबसे बड़े और सबसे छोटे eigenvalues ​​हैं $W$. परिभाषित करना ${\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$, साथ $W$ ऊपरोक्त अनुसार। तब:

$\chi _{H}(G)\leq \chi (G).$

वेक्टर रंगीन संख्या: होने देना $W$ एक धनात्मक अर्ध-निश्चित मैट्रिक्स हो जैसे कि $W_{i,j}\leq -{\tfrac {1}{k-1}}$ जब कभी भी $(i,j)$ में बढ़त है $G$ परिभाषित करना $\chi _{V}(G)$ कम से कम k जिसके लिए $W$ ऐसा मैट्रिक्स उपस्थित हो तब:

$\chi _{V}(G)\leq \chi (G).$

लोवाज़ संख्या: एक पूरक ग्राफ की लोवाज़ संख्या भी रंगीन संख्या पर एक निचली सीमा है:

$\vartheta ({\bar {G}})\leq \chi (G).$

भिन्नात्मक वर्णिक संख्या: किसी ग्राफ की भिन्नात्मक वर्णिक संख्या वर्णिक संख्या पर भी निचली सीमा होती है:

$\chi _{f}(G)\leq \chi (G).$

इन सीमाओं का क्रम इस प्रकार है:

$\chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).$

उच्च रंगीन संख्या वाले रेखांकन

बड़े क्लिक (ग्राफ़ सिद्धांत) वाले ग्राफ़ में उच्च रंगीन संख्या होती है, लेकिन विपरीत सत्य नहीं है। ग्रॉट्ज़स्च ग्राफ़ एक त्रिकोण के बिना 4-रंगीन ग्राफ़ का एक उदाहरण है, और उदाहरण को Mycielskian के लिए सामान्यीकृत किया जा सकता है।

प्रमेय (William T. Tutte 1947, Alexander Zykov 1949, Jan Mycielski 1955): मनमाने ढंग से उच्च रंग संख्या के साथ त्रिभुज-मुक्त ग्राफ़ उपस्थित हैं।

यह साबित करने के लिए, माइसील्स्की और ज़्यकोव दोनों ने, प्रत्येक ने त्रिभुज-मुक्त ग्राफ़ के आगमनात्मक रूप से परिभाषित परिवार का निर्माण किया, लेकिन मनमाने ढंग से बड़ी रंगीन संख्या के साथ। बर्लिंग (1965) निर्मित अक्ष संरेखित बक्से में $\mathbb {R} ^{3}$ जिसका प्रतिच्छेदन ग्राफ त्रिभुज-मुक्त है और ठीक से रंगने के लिए मनमाने ढंग से कई रंगों की आवश्यकता होती है। ग्राफ़ के इस परिवार को बर्लिंग ग्राफ़ कहा जाता है। पावलिक एट अल द्वारा दिए गए सतह में त्रिभुज-मुक्त रेखा खंडों के एक परिवार के निर्माण के लिए ग्राफ़ के समान वर्ग का उपयोग किया जाता है। (2014)। यह दर्शाता है कि इसके प्रतिच्छेदन ग्राफ की रंगीन संख्या भी मनमाने ढंग से बड़ी है। इसलिए, इसका तात्पर्य है कि अक्ष संरेखित बक्से में $\mathbb {R} ^{3}$ साथ ही लाइन सेगमेंट में $\mathbb {R} ^{2}$ χ-बाध्य नहीं हैं।

ब्रूक्स के प्रमेय से, उच्च रंगीन संख्या वाले ग्राफ़ में उच्च अधिकतम डिग्री होनी चाहिए। लेकिन रंगीनता पूरी तरह से स्थानीय घटना नहीं है: उच्च गर्थ (ग्राफ सिद्धांत) वाला एक ग्राफ स्थानीय रूप से पेड़ की तरह दिखता है, क्योंकि सभी चक्र लंबे होते हैं, लेकिन इसकी रंगीन संख्या 2 नहीं होनी चाहिए:

प्रमेय (पॉल एर्डोस | एर्डोस): मनमाने ढंग से उच्च परिधि और रंगीन संख्या के ग्राफ उपस्थित हैं।

रंगीन सूचकांक पर सीमा

जी का किनारा रंग इसके लाइन ग्राफ का शीर्ष रंग है $L(G)$, और इसके विपरीत, इस प्रकार

$\chi '(G)=\chi (L(G)).$

किनारे की रंगीनता और ग्राफ की अधिकतम डिग्री के बीच एक मजबूत संबंध है $\Delta (G)$. चूंकि सभी किनारों को एक ही शीर्ष पर घटना के लिए अपने स्वयं के रंग की आवश्यकता होती है, हमारे पास है

$\chi '(G)\geq \Delta (G).$

इसके अतिरिक्त,

कोनिग प्रमेय (ग्राफ सिद्धांत)|कोनिग प्रमेय: $\chi '(G)=\Delta (G)$ यदि G द्विदलीय है।

सामान्य तौर पर, संबंध ब्रूक्स के प्रमेय से भी अधिक मजबूत होता है जो वर्टेक्स कलरिंग के लिए देता है:

'वाइज़िंग का प्रमेय|वाइज़िंग का प्रमेय:' अधिकतम डिग्री का एक ग्राफ $\Delta$ बढ़त-रंगीन संख्या है $\Delta$ या $\Delta +1$.

अन्य गुण

एक ग्राफ में के-रंग होता है अगर और केवल अगर इसमें एक चक्रीय अभिविन्यास होता है जिसके लिए सबसे लंबे पथ की लंबाई अधिकतर के होती है; यह गैलाई-हस्से-रॉय-विटावर प्रमेय है (Nešetřil & Ossona de Mendez 2012).

प्लानर ग्राफ़ के लिए, वर्टेक्स कलरिंग अनिवार्य रूप से दोहरे से कहीं नहीं-शून्य प्रवाह हैं।

अनंत रेखांकन के बारे में बहुत कम जानकारी है।

अनंत ग्राफ कलरिंग के बारे में कुछ परिणामों में से दो निम्नलिखित हैं:

• यदि एक अनंत ग्राफ जी के सभी परिमित सबग्राफ के-रंगीन हैं, तो पसंद के स्वयंसिद्ध की धारणा के तहत जी भी है। यह डी ब्रुजन-एर्दोस प्रमेय (ग्राफ सिद्धांत) है | de Bruijn & Erdős (1951).
• यदि कोई ग्राफ़ प्रत्येक n ≥ n₀ के लिए पूर्ण n-रंग स्वीकार करता है, यह एक अनंत पूर्ण रंग को स्वीकार करता है (Fawcett 1978).

प्रारंभिक समस्याएं

जैसा कि ऊपर कहा, $\omega (G)\leq \chi (G)\leq \Delta (G)+1.$ 1998 से रीड का एक अनुमान यह है कि मूल्य अनिवार्य रूप से निचली सीमा के करीब है,

$\chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .$

हैडविगर-नेल्सन समस्या, जहां इकाई दूरी होने पर दो बिंदु आसन्न होते हैं, अज्ञात है, हालांकि यह 5, 6, या 7 में से एक है। गणित की अन्य अनसुलझी समस्याओं में रेखांकन की रंगीन संख्या से संबंधित हैडविगर अनुमान (ग्राफ सिद्धांत) सम्मिलित हैं। ) यह बताते हुए कि रंगीन संख्या के साथ प्रत्येक ग्राफ में ग्राफ माइनर के रूप में के कोने पर एक पूर्ण ग्राफ होता है, एर्डोस-फैबर-लोवाज़ अनुमान पूरे ग्राफ के यूनियनों की रंगीन संख्या को सीमित करता है जिसमें प्रत्येक जोड़ी के लिए सामान्यतः अधिकतम एक शीर्ष होता है, और अल्बर्टसन का अनुमान है कि के-क्रोमैटिक ग्राफ़ के बीच पूर्ण ग्राफ़ सबसे छोटे क्रॉसिंग नंबर (ग्राफ़ सिद्धांत) वाले होते हैं।

जब बिरखॉफ और लुईस ने चार-रंग प्रमेय पर अपने हमले में रंगीन बहुपद पेश किया, तो उन्होंने अनुमान लगाया कि प्लानर ग्राफ जी के लिए, बहुपद $P(G,t)$ क्षेत्र में कोई शून्य नहीं है $[4,\infty )$. हालांकि यह ज्ञात है कि इस तरह के रंगीन बहुपद का क्षेत्र में कोई शून्य नहीं है $[5,\infty )$ ओर वो $P(G,4)\neq 0$, उनका अनुमान अभी भी अनसुलझा है। यह भी एक अनसुलझी समस्या बनी हुई है कि ग्राफ़ को चित्रित करने के लिए जिसमें एक ही रंगीन बहुपद है और यह निर्धारित करने के लिए कि कौन से बहुपद रंगीन हैं।

एल्गोरिदम

ग्राफ रंगना
Decision
Name	Graph coloring, vertex coloring, k-coloring
Input	Graph G with n vertices. Integer k
Output	Does G admit a proper vertex coloring with k colors?
Running time	O(2 nn)
Complexity	NP-complete
Reduction from	3-Satisfiability
Garey–Johnson	GT4
Optimisation
Name	Chromatic number
Input	Graph G with n vertices.
Output	χ(G)
Complexity	NP-hard
Approximability	O(n (log n)−3(log log n)2)
Inapproximability	O(n1−ε) unless P = NP
Counting problem
Name	Chromatic polynomial
Input	Graph G with n vertices. Integer k
Output	The number P (G,k) of proper k-colorings of G
Running time	O(2 nn)
Complexity	#P-complete
Approximability	FPRAS for restricted cases
Inapproximability	No PTAS unless P = NP

बहुपद समय

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

यदि ग्राफ़ प्लानर है और कम शाखा-चौड़ाई है (या गैर-प्लानर है लेकिन ज्ञात शाखा अपघटन के साथ), तो इसे गतिशील प्रोग्रामिंग का उपयोग करके बहुपद समय में हल किया जा सकता है। सामान्य तौर पर, आवश्यक समय ग्राफ़ आकार में बहुपद होता है, लेकिन शाखा-चौड़ाई में घातीय होता है।

सटीक एल्गोरिदम

के-कलरिंग के लिए क्रूर-बल खोज इनमें से प्रत्येक पर विचार करता है $k^{n}$ n रंगों को k रंगों का असाइनमेंट और यदि यह कानूनी है तो प्रत्येक के लिए जाँच करता है। रंगीन संख्या और रंगीन बहुपद की गणना करने के लिए, इस प्रक्रिया का उपयोग प्रत्येक के लिए किया जाता है $k=1,\ldots ,n-1$, सबसे छोटे इनपुट ग्राफ़ को छोड़कर सभी के लिए अव्यावहारिक।

गतिशील प्रोग्रामिंग और अधिकतम स्वतंत्र सेट की संख्या पर बाध्यता का उपयोग करके, समय और स्थान में k-रंगशीलता का निर्णय लिया जा सकता है $O(2.4423^{n})$. समावेशन-बहिष्करण के सिद्धांत और फ्रैंक येट्स के एल्गोरिदम का उपयोग तेजी से जीटा परिवर्तन के लिए, समय में k-रंगशीलता का निर्णय लिया जा सकता है $O(2^{n}n)$ किसी के लिए तेज़ एल्गोरिदम को 3- और 4-रंगशीलता के लिए जाना जाता है, जिसे समय पर तय किया जा सकता है $O(1.3289^{n})$ और $O(1.7272^{n})$, क्रमश। घातीय रूप से तेज़ एल्गोरिदम 5- और 6-रंगशीलता के साथ-साथ विरल ग्राफ़ सहित ग्राफ़ के प्रतिबंधित परिवारों के लिए भी जाने जाते हैं।

संकुचन

संकुचन (ग्राफ सिद्धांत) $G/uv$ एक ग्राफ जी का ग्राफ u और v की पहचान करके और उनके बीच के किनारों को हटाकर प्राप्त किया गया ग्राफ है। मूल रूप से u या v के लिए शेष शेष किनारे अब उनकी पहचान (यानी, नया फ्यूज्ड नोड uv) के लिए प्रासंगिक हैं। यह ऑपरेशन ग्राफ कलरिंग के विश्लेषण में एक प्रमुख भूमिका निभाता है।

वर्णिक संख्या पुनरावृत्ति संबंध को संतुष्ट करती है:

$\chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}$

इस कारण Zykov (1949), जहाँ u और v असन्निकट शीर्ष हैं, और $G+uv$ किनारे के साथ ग्राफ है uv जोड़ा गया। कई एल्गोरिदम इस पुनरावृत्ति के मूल्यांकन पर आधारित हैं और परिणामी संगणना वृक्ष को कभी-कभी ज़ीकोव वृक्ष कहा जाता है। चलने का समय यू और वी को चुनने के लिए एक अनुमानी पर आधारित है।

रंगीन बहुपद निम्नलिखित पुनरावृत्ति संबंध को संतुष्ट करता है

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

जहाँ u और v आसन्न शीर्ष हैं, और $G-uv$ किनारे के साथ ग्राफ है uv निकाला गया। $P(G-uv,k)$ ग्राफ़ के संभावित उचित रंगों की संख्या का प्रतिनिधित्व करता है, जहाँ शीर्षों में समान या भिन्न रंग हो सकते हैं। फिर दो अलग-अलग ग्राफों से उचित रंग उत्पन्न होते हैं। व्याख्या करने के लिए, यदि शीर्षों u और v के अलग-अलग रंग हैं, तो हम एक ग्राफ़ पर भी विचार कर सकते हैं जहाँ u और v आसन्न हैं। यदि यू और वी के समान रंग हैं, तो हम एक ग्राफ पर भी विचार कर सकते हैं जहां यू और वी अनुबंधित हैं। टुट्टे की जिज्ञासा जिसके बारे में अन्य ग्राफ गुण इस पुनरावृत्ति को संतुष्ट करते हैं, ने उन्हें रंगीन बहुपद, टुट्टे बहुपद के द्विभाजित सामान्यीकरण की खोज करने के लिए प्रेरित किया।

ये भाव विलोपन-संकुचन एल्गोरिथम नामक एक पुनरावर्ती प्रक्रिया को जन्म देते हैं, जो ग्राफ़ रंग के लिए कई एल्गोरिदम का आधार बनाती है। चलने का समय फाइबोनैचि संख्यााओं के समान पुनरावृत्ति संबंध को संतुष्ट करता है, इसलिए सबसे खराब स्थिति में एल्गोरिदम बहुपद कारक के भीतर समय पर चलता है $\left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})$ n शीर्षों और m किनारों के लिए। संख्या के एक बहुपद कारक के भीतर विश्लेषण $t(G)$ इनपुट ग्राफ के फैले हुए (गणित) में सुधार किया जा सकता है। अभ्यास में, कुछ पुनरावर्ती कॉलों से बचने के लिए शाखा और बाध्य रणनीतियों और समरूपता अस्वीकृति को नियोजित किया जाता है। रनिंग टाइम वर्टेक्स पेयर को चुनने के लिए उपयोग किए गए ह्यूरिस्टिक पर निर्भर करता है।

लोभी रंग

Main article: लोभी रंग

अलग-अलग वर्टेक्स ऑर्डर का उपयोग करते हुए एक ही ग्राफ के दो लोभी रंग। सही उदाहरण एन कोने के साथ 2-रंगीन ग्राफों को सामान्यीकृत करता है, जहां लालची एल्गोरिदम खर्च करता है $n/2$ रंग की।

लालची एल्गोरिथ्म एक विशिष्ट क्रम में कोने पर विचार करता है $v_{1}$,…,$v_{n}$ और असाइन करता है $v_{i}$ सबसे छोटा उपलब्ध रंग जिसका उपयोग नहीं किया गया $v_{i}$के पड़ोसियों में $v_{1}$,…,$v_{i-1}$, यदि आवश्यक हो तो एक नया रंग जोड़ना। परिणामी रंग की गुणवत्ता चुने हुए क्रम पर निर्भर करती है। एक आदेश उपस्थित है जो इष्टतम संख्या के साथ एक लोभी रंग की ओर जाता है $\chi (G)$ रंग की। दूसरी ओर, लोभी रंग मनमाने ढंग से खराब हो सकते हैं; उदाहरण के लिए, n शीर्षों पर क्राउन ग्राफ 2-रंग का हो सकता है, लेकिन इसमें एक क्रम है जो एक लोभी रंग की ओर जाता है $n/2$ रंग की।

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

यदि शीर्षों को उनकी डिग्री (ग्राफ़ सिद्धांत) के अनुसार क्रमबद्ध किया जाता है, तो परिणामी लोभी रंग अधिक से अधिक उपयोग करता है ${\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}$ रंग, अधिक से अधिक एक ग्राफ़ की अधिकतम डिग्री से अधिक। इस अनुमानी को कभी-कभी वेल्श-पॉवेल एल्गोरिथम कहा जाता है। डैनियल ब्रेलाज़ के कारण एक और अनुमानी|ब्रेलाज़ गतिशील रूप से क्रम स्थापित करता है जबकि एल्गोरिथम आगे बढ़ता है, विभिन्न रंगों की सबसे बड़ी संख्या के निकट शीर्ष को चुनता है। कई अन्य ग्राफ़ कलरिंग ह्यूरिस्टिक्स समान रूप से एक विशिष्ट स्थैतिक या गतिशील रणनीति के लिए लोभी रंग पर आधारित होते हैं, इन एल्गोरिदम को कभी-कभी अनुक्रमिक रंग एल्गोरिदम कहा जाता है।

इस संख्या को अधिकतम करने के लिए चुने गए वर्टेक्स ऑर्डरिंग का उपयोग करके, लालची एल्गोरिथ्म द्वारा प्राप्त किए जा सकने वाले रंगों की अधिकतम (सबसे खराब) संख्या को ग्राफ की ग्रुंडी संख्या कहा जाता है।

ह्यूरिस्टिक एल्गोरिदम

ग्राफ़ कलरिंग के लिए दो प्रसिद्ध बहुपद-समय अनुमानी डीसैटूर और रिकर्सिव सबसे बड़ा पहला एल्गोरिथम (RLF) एल्गोरिदम हैं।

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

पुनरावर्ती सबसे बड़ा पहला एल्गोरिदम एक समय में प्रत्येक रंग वर्ग का निर्माण करके एक अलग तरीके से संचालित होता है। यह विशिष्ट ह्यूरिस्टिक नियमों का उपयोग करके ग्राफ़ में अधिकतम स्वतंत्र वर्टिकल सेट की पहचान करके ऐसा करता है। यह फिर इन शीर्षों को एक ही रंग में निर्दिष्ट करता है और उन्हें ग्राफ़ से हटा देता है। इन क्रियाओं को शेष सबग्राफ पर तब तक दोहराया जाता है जब तक कि कोई शीर्ष न रह जाए।

डीसैटूर की सबसे खराब स्थिति जटिलता है $O(n^{2})$, कहाँ $n$ ग्राफ में शीर्षों की संख्या है। एल्गोरिदम को संतृप्ति डिग्री स्टोर करने के लिए बाइनरी ढेर का उपयोग करके भी कार्यान्वित किया जा सकता है $O((n+m)\log n)$ कहाँ $m$ ग्राफ में किनारों की संख्या है। यह विरल रेखांकन के साथ बहुत तेजी से चलता है। RLF की समग्र जटिलता डीसैटूर की तुलना में थोड़ी अधिक है ${\mathcal {O}}(mn)$.

डीसैटूर और RLF द्विदलीय ग्राफ़, चक्र ग्राफ और पहिया ग्राफ के लिए सटीक एल्गोरिथम हैं।

समानांतर और वितरित एल्गोरिदम

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

एक सममित ग्राफ में, एक नियतात्मक एल्गोरिथ्म वितरित एल्गोरिथ्म एक उचित शीर्ष रंग नहीं खोज सकता है। सममिति को तोड़ने के लिए कुछ सहायक सूचनाओं की आवश्यकता होती है। एक मानक धारणा यह है कि प्रारंभ में प्रत्येक नोड में एक अद्वितीय पहचानकर्ता होता है, उदाहरण के लिए, सेट {1, 2, ..., n} से। अन्यथा रखो, हम मानते हैं कि हमें एक n-रंग दिया गया है। रंगों की संख्या को n से घटाकर, उदाहरण के लिए, Δ+ 1 करने की चुनौती है। अधिक रंगों का उपयोग किया जाता है, उदा. Δ+1 के बजाय O(Δ), संचार के कम दौर की आवश्यकता होती है।

(Δ + 1)-कलरिंग के लिए लालची एल्गोरिथम का एक सीधा वितरित संस्करण सबसे खराब स्थिति में Θ(n) संचार दौर की आवश्यकता है - सूचना को नेटवर्क के एक तरफ से दूसरी तरफ प्रचारित करने की आवश्यकता हो सकती है।

सबसे सरल दिलचस्प स्थिति एक n-साइकिल ग्राफ है। रिचर्ड कोल और उजी विस्किन दिखाएँ कि एक वितरित एल्गोरिथम है जो एक तुल्यकालिक संचार चरण में रंगों की संख्या को n से O(log n) तक कम कर देता है। उसी प्रक्रिया को दोहराकर, ओ में एक n-चक्र का 3-रंग प्राप्त करना संभव है (log*n) संचार चरण (यह मानते हुए कि हमारे पास अद्वितीय नोड पहचानकर्ता हैं)।

फ़ंक्शन log*, पुनरावृत्त लघुगणक, एक अत्यंत लगभग स्थिर धीरे-धीरे बढ़ने वाला कार्य है, इसलिए कोल और विस्किन के नतीजे ने सवाल उठाया कि क्या n-चक्र को 3-रंग देने के लिए निरंतर समय वितरित एल्गोरिदम है या नहीं। Linial (1992) दिखाया कि यह संभव नहीं है: किसी भी नियतात्मक वितरित एल्गोरिथ्म के लिए Ω(log* n) एक n-चक्र में एक n-रंग को 3-रंग में कम करने के लिए संचार कदम है।

कोल और विस्किन की तकनीक को मनमाना बाउंड-डिग्री ग्राफ़ में भी लागू किया जा सकता है; रनिंग टाइम पॉली (Δ) + हे (log*n)। श्नाइडर एट अल द्वारा तकनीक को यूनिट डिस्क ग्राफ तक बढ़ाया गया था। छोटे Δ के लिए (Δ + 1)-कलरिंग के लिए सबसे तेज़ नियतात्मक एल्गोरिदम लियोनिद बारेनबोइम, माइकल एलकिन और फैबियन कुह्न के कारण हैं। बारेनबोइम एट अल द्वारा एल्गोरिथम। समय O(Δ) + में चलता है log*(n)/2, जो कि n के संदर्भ में इष्टतम है क्योंकि लिनियल की निचली सीमा के कारण स्थिर कारक 1/2 में सुधार नहीं किया जा सकता है। Panconesi & Srinivasan (1996) समय में Δ+1 कलरिंग की गणना करने के लिए नेटवर्क डिकंपोज़िशन $2^{O\left({\sqrt {\log n}}\right)}$का उपयोग करें।

वितरित मॉडल में किनारों के रंग की समस्या का भी अध्ययन किया गया है। पैनकोनेसी और रिज़ी (2001) इस मॉडल में O(Δ + log* n) समय में (2Δ - 1)-कलरिंग प्राप्त करते हैं। लिनियल (1992) के कारण वितरित वर्टेक्स कलरिंग के लिए निचली सीमा वितरित एज कलरिंग समस्या पर भी लागू होती है।

विकेंद्रीकृत एल्गोरिदम

विकेंद्रीकृत एल्गोरिदम वे हैं जहां कोई संदेश देना की अनुमति नहीं है (वितरित एल्गोरिदम के विपरीत जहां स्थानीय संदेश पास होता है), और कुशल विकेन्द्रीकृत एल्गोरिदम उपस्थित हैं जो उचित रंग उपस्थित होने पर ग्राफ को रंग देंगे। ये मानते हैं कि एक शीर्ष यह समझने में सक्षम है कि क्या उसका कोई पड़ोसी शीर्ष के समान रंग का उपयोग कर रहा है, चाहे कोई स्थानीय संघर्ष उपस्थित हो। यह कई अनुप्रयोगों में एक हल्की धारणा है उदा। वायरलेस चैनल आवंटन में सामान्यतः यह मान लेना उचित है कि एक स्टेशन यह पता लगाने में सक्षम होगा कि क्या अन्य हस्तक्षेप करने वाले ट्रांसमीटर उसी चैनल का उपयोग कर रहे हैं (उदाहरण के लिए एसआईएनआर को मापकर)। यह सेंसिंग जानकारी सीखने के ऑटोमेटा पर आधारित एल्गोरिदम को प्रायिकता के साथ एक उचित ग्राफ रंग खोजने के लिए पर्याप्त है।

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

ग्राफ़ रंग करना कम्प्यूटेशनल रूप से कठिन है। यह तय करने के लिए एनपी-सम्पूर्ण है कि क्या दिया गया ग्राफ k ∈ {0,1,2} मामलों को छोड़कर किसी दिए गए k के लिए k- रंग स्वीकार करता है। विशेष रूप से, रंगीन संख्या की गणना करना एनपी-हार्ड है। 4-रेगुलर प्लानर ग्राफ़ पर भी 3-कलरिंग प्रॉब्लम NP-कंप्लीट रहती है। अधिकतम डिग्री 3 या उससे कम वाले ग्राफ़ पर, हालांकि, ब्रूक्स प्रमेय का तात्पर्य है कि 3-रंग की समस्या को रैखिक समय में हल किया जा सकता है। इसके अलावा, प्रत्येक k > 3 के लिए, चार रंग प्रमेय द्वारा एक प्लानर ग्राफ का k-रंग उपस्थित है, और बहुपद समय में इस तरह के रंग को खोजना संभव है।

सबसे प्रसिद्ध सन्निकटन एल्गोरिथम एक कारक O(n(log log n)²(log n)⁻³) के भीतर आकार के रंग की गणना करता है। सभी ε > 0 के लिए, n^1−ε के भीतर रंगीन संख्या का अनुमान लगाना एनपी-हार्ड है।

3-रंगीय ग्राफ को 4 रंगों से रंगना भी एनपी-हार्ड है और k के साथ k^{(log k ) / 25} पर्याप्त रूप से बड़े स्थिरांक k के लिए रंग है।

रंगीन बहुपद के गुणांकों की गणना Sharp-P-complete|#P-hard है। वास्तव में, के मूल्य की गणना भी $\chi (G,k)$ k = 1 और k = 2 को छोड़कर किसी भी तर्कसंगत बिंदु k पर #P-हार्ड है। np (जटिलता) = आरपी (जटिलता) को छोड़कर किसी भी तर्कसंगत बिंदु k ≥ 1.5 पर रंगीन बहुपद का मूल्यांकन करने के लिए कोई एफपीआरएएस नहीं है। एज कलरिंग के लिए, वाइज़िंग के परिणाम का प्रमाण एक एल्गोरिथम देता है जो अधिकतम Δ+1 रंगों का उपयोग करता है। हालांकि, किनारे के रंगीन संख्या के लिए दो उम्मीदवार मूल्यों के बीच निर्णय लेना एनपी-सम्पूर्ण है। सन्निकटन एल्गोरिदम के संदर्भ में, Wiesing के एल्गोरिथ्म से पता चलता है कि किनारे की रंगीन संख्या को 4/3 के भीतर अनुमानित किया जा सकता है, और कठोरता के परिणाम से पता चलता है कि नहीं (4/3 - ε) - एल्गोरिथम का उपयोग किसी भी ε> के लिए उपस्थित है 0 जब तक p = np। सन्निकटन एल्गोरिदम के साहित्य में ये सबसे पुराने परिणामों में से हैं, भले ही कोई भी पेपर उस धारणा का स्पष्ट उपयोग नहीं करता है।

अनुप्रयोग

निर्धारण

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

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

रजिस्टर आवंटन

Main article: आवंटन रजिस्टर करें

कंपाइलर एक कंप्यूटर प्रोग्राम है जो एक कंप्यूटर भाषा का दूसरे में अनुवाद करता है। परिणामी कोड के निष्पादन समय में सुधार करने के लिए, [[संकलक अनुकूलन]] की तकनीकों में से एक रजिस्टर आवंटन है, जहां संकलित प्रोग्राम के सबसे अधिक उपयोग किए जाने वाले मूल्यों को तेज प्रोसेसर रजिस्टरों में रखा जाता है। आदर्श रूप से, मूल्यों को रजिस्टरों को सौंपा जाता है ताकि जब वे उपयोग किए जाएं तो वे सभी रजिस्टरों में रह सकें।

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

अन्य अनुप्रयोग

ग्राफ कलरिंग की समस्या कई व्यावहारिक क्षेत्रों में उत्पन्न होती है जैसे पैटर्न मिलान, खेल शेड्यूलिंग, बैठने की योजना तैयार करना, परीक्षा समय सारिणी, टैक्सी शेड्यूल करना और सुडोकू पहेली को हल करना है।

अन्य रंग

रैमसे सिद्धांत

Main article: रैमसे सिद्धांत

रैमसे सिद्धांत में अनुचित रंग समस्याओं का एक महत्वपूर्ण वर्ग का अध्ययन किया जाता है, जहां ग्राफ के किनारों को रंगों को सौंपा गया है, और घटना किनारों के रंगों पर कोई प्रतिबंध नहीं है। एक साधारण उदाहरण दोस्तों और अजनबियों पर प्रमेय है, जो बताता है कि किनारों के किसी भी रंग में $K_{6}$, छह शीर्षों का पूरा ग्राफ, एकवर्णी त्रिभुज होगा; प्रायः यह कहकर सचित्र किया जाता है कि छह लोगों के किसी भी समूह में या तो तीन पारस्परिक अजनबी हैं या तीन पारस्परिक परिचित हैं। रैमसे सिद्धांत इस विचार के सामान्यीकरण से संबंधित है, ताकि अव्यवस्था के बीच नियमितता की तलाश की जा सके, दी गई संरचना के साथ मोनोक्रोमैटिक सबग्राफ के अस्तित्व के लिए सामान्य स्थितियों का पता लगाया जा सके।

अन्य रंग

सन्निकट-शीर्ष-विभेदक-कुल रंग

अतिरिक्त प्रतिबंध के साथ एक कुल रंग जो किसी भी दो आसन्न कोने में अलग-अलग रंग सेट होते हैं

चक्रीय रंग

हर 2-क्रोमैटिक सबग्राफ एसाइक्लिक है

बी-रंग

कोने का रंग जहां प्रत्येक रंग वर्ग में एक शीर्ष होता है जिसमें अन्य सभी रंग वर्गों में पड़ोसी होता है।

वृत्ताकार रंग

कार्य प्रणालियों द्वारा प्रेरित जिसमें उत्पादन चक्रीय तरीके से आगे बढ़ता है

कोकलरिंग

एक अनुचित वर्टेक्स कलरिंग जहां हर रंग वर्ग एक स्वतंत्र सेट या एक क्लिक को प्रेरित करता है

पूर्ण रंगाई

रंगों का प्रत्येक जोड़ा कम से कम एक किनारे पर दिखाई देता है

दोषपूर्ण रंग

एक अनुचित शीर्ष रंग जहां हर रंग वर्ग एक परिबद्ध डिग्री सबग्राफ को प्रेरित करता है।

विशिष्ट रंग

एक अनुचित शीर्ष रंग जो ग्राफ के सभी समरूपता को नष्ट कर देता है

एकसमान रंग

रंग वर्गों के आकार अधिक से अधिक एक से भिन्न होते हैं

सटीक रंग

रंगों का हर जोड़ा ठीक एक किनारे पर दिखाई देता है

भिन्नात्मक रंग

शीर्षों में कई रंग हो सकते हैं, और प्रत्येक किनारे पर प्रत्येक शीर्ष के रंग भागों का योग एक से अधिक नहीं होता है

हैमिल्टनियन रंग

दो शीर्षों के बीच सबसे लंबे पथ की लंबाई का उपयोग करता है, जिसे डेटोर दूरी भी कहा जाता है

सुरीले रंग

रंगों का हर जोड़ा अधिकतम एक किनारे पर दिखाई देता है

घटना रंग

शीर्ष और किनारे की प्रत्येक आसन्न घटना अलग-अलग रंगों से रंगी होती है

अंतराल किनारे का रंग

कॉमन वर्टेक्स में मिलने वाले किनारों का रंग सन्निहित होना चाहिए

सूची का रंग

प्रत्येक शीर्ष रंगों की सूची में से चुनता है

[[एजबी रंग की सूची बनाएं]]

प्रत्येक किनारा रंगों की सूची में से चुनता है

L(h, k)-रंग

आसन्न शीर्षों पर रंगों का अंतर कम से कम h है और दो दूरी पर शीर्षों के रंगों का अंतर कम से कम k है। एक विशेष मामला एल (2,1) -कलरिंग है।

उन्मुख रंग

ग्राफ के किनारों के ओरिएंटेशन को ध्यान में रखता है

पथ रंगना

ग्राफ़ में रूटिंग समस्या को मॉडल करता है

रेडियो रंग

शीर्षों के बीच की दूरी और उनके रंगों के अंतर का योग k+1 से अधिक है, जहां k एक धनात्मक पूर्णांक है।

रैंक रंग

यदि दो शीर्षों का रंग समान है, तो उनके बीच के प्रत्येक पथ में i से अधिक रंग वाला एक शीर्ष होता है

उपरंग

एक अनुचित शीर्ष रंग जहां हर रंग वर्ग गुटों के संघ को प्रेरित करता है

राशि का रंग

न्यूनीकरण की कसौटी रंगों का योग है

सितारा रंगना

हर 2-क्रोमैटिक सबग्राफ स्टार का एक अलग संग्रह है (ग्राफ सिद्धांत)

मजबूत रंग

प्रत्येक रंग समान आकार के प्रत्येक विभाजन में ठीक एक बार दिखाई देता है

मजबूत किनारे का रंग

किनारों को इस तरह से रंगा जाता है कि प्रत्येक रंग वर्ग एक मिलान को प्रेरित करता है (रेखा ग्राफ के वर्ग को रंगने के बराबर)

टी-कलरिंग

आसन्न शीर्षों के दो रंगों के बीच के अंतर का निरपेक्ष मान निश्चित सेट टी से संबंधित नहीं होना चाहिए

कुल रंगाई

कोने और किनारे रंगीन होते हैं

वृक्ष-गहराई

प्रत्येक जुड़े प्रेरित सबग्राफ में एक रंग होता है जो ठीक एक बार उपयोग किया जाता है

एकवर्णी त्रिभुज|त्रिभुज-मुक्त किनारा रंग

किनारों को रंगीन किया जाता है ताकि प्रत्येक रंग वर्ग एक त्रिभुज-मुक्त ग्राफ़ बना सके|त्रिकोण-मुक्त सबग्राफ

कमजोर रंग

एक अनुचित शीर्ष रंग जहां प्रत्येक गैर-पृथक नोड में एक अलग रंग के साथ कम से कम एक पड़ोसी होता है

रंग को हस्ताक्षरित रेखांकन और लाभ रेखांकन के लिए भी माना जा सकता है।

यह भी देखें

• गंभीर ग्राफ
• ग्राफ रंग खेल
• ग्राफ समरूपता
• हजोस निर्माण
• सुडोकू का गणित
• बहुपक्षीय ग्राफ
• विशिष्ट रंगीन ग्राफ

संदर्भ

• Barenboim, L.; Elkin, M. (2009), "Distributed (Δ + 1)-coloring in linear (in Δ) time", Proceedings of the 41st Symposium on Theory of Computing, pp. 111–120, arXiv:0812.1379, doi:10.1145/1536414.1536432, ISBN 978-1-60558-506-2, S2CID 13446345
• Beigel, R.; Eppstein, D. (2005), "3-coloring in time O(1.3289ⁿ)", Journal of Algorithms, 54 (2)): 168–204, arXiv:cs/0006046, doi:10.1016/j.jalgor.2004.06.008, S2CID 1209067
• Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), "Set partitioning via inclusion–exclusion", SIAM Journal on Computing, 39 (2): 546–563, doi:10.1137/070683933
• Brélaz, D. (1979), "New methods to color the vertices of a graph", Communications of the ACM, 22 (4): 251–256, doi:10.1145/359094.359101, S2CID 14838769
• Brooks, R. L. (1941), "On colouring the nodes of a network", Proceedings of the Cambridge Philosophical Society, 37 (2): 194–197, Bibcode:1941PCPS...37..194B, doi:10.1017/S030500410002168X, S2CID 209835194
• de Bruijn, N. G.; Erdős, P. (1951), "A colour problem for infinite graphs and a problem in the theory of relations" (PDF), Nederl. Akad. Wetensch. Proc. Ser. A, 54: 371–373, doi:10.1016/S1385-7258(51)50053-7, archived from the original (PDF) on 2016-03-10, retrieved 2009-05-16 (= Indag. Math. 13)
• Byskov, J.M. (2004), "Enumerating maximal independent sets with applications to graph colouring", Operations Research Letters, 32 (6): 547–556, doi:10.1016/j.orl.2004.03.002

• Chaitin, G. J. (1982), "Register allocation & spilling via graph colouring", Proc. 1982 SIGPLAN Symposium on Compiler Construction, pp. 98–105, doi:10.1145/800230.806984, ISBN 0-89791-074-5, S2CID 16872867
• Cole, R.; Vishkin, U. (1986), "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control, 70 (1): 32–53, doi:10.1016/S0019-9958(86)80023-7
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. (1990), Introduction to Algorithms (1st ed.), The MIT Press
• Crescenzi, P.; Kann, V. (December 1998), "How to find the best approximation results — a follow-up to Garey and Johnson", ACM SIGACT News, 29 (4): 90, doi:10.1145/306198.306210, S2CID 15748200
• Dailey, D. P. (1980), "Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete", Discrete Mathematics, 30 (3): 289–293, doi:10.1016/0012-365X(80)90236-8
• Duffy, K.; O'Connell, N.; Sapozhnikov, A. (2008), "Complexity analysis of a decentralised graph colouring algorithm" (PDF), Information Processing Letters, 107 (2): 60–63, doi:10.1016/j.ipl.2008.01.002
• Fawcett, B. W. (1978), "On infinite full colourings of graphs", Can. J. Math., 30 (3): 455–457, doi:10.4153/cjm-1978-039-8, S2CID 123812465

• Fomin, F.V.; Gaspers, S.; Saurabh, S. (2007), "Improved Exact Algorithms for Counting 3- and 4-Colorings", Proc. 13th Annual International Conference, COCOON 2007, Lecture Notes in Computer Science, vol. 4598, Springer, pp. 65–74, doi:10.1007/978-3-540-73545-8_9, ISBN 978-3-540-73544-1
• Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5
• Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47–63, doi:10.1145/800119.803884, ISBN 9781450374231, S2CID 207693360
• Goldberg, L. A.; Jerrum, M. (July 2008), "Inapproximability of the Tutte polynomial", Information and Computation, 206 (7): 908–929, arXiv:cs/0605140, doi:10.1016/j.ic.2008.04.003, S2CID 53304001
• Goldberg, A. V.; Plotkin, S. A.; Shannon, G. E. (1988), "Parallel symmetry-breaking in sparse graphs", SIAM Journal on Discrete Mathematics, 1 (4): 434–446, doi:10.1137/0401044
• Guruswami, V.; Khanna, S. (2000), "On the hardness of 4-coloring a 3-colorable graph", Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pp. 188–197, doi:10.1109/CCC.2000.856749, ISBN 0-7695-0674-7, S2CID 47551585
• Halldórsson, M. M. (1993), "A still better performance guarantee for approximate graph coloring", Information Processing Letters, 45: 19–23, doi:10.1016/0020-0190(93)90246-6
• Holyer, I. (1981), "The NP-completeness of edge-coloring", SIAM Journal on Computing, 10 (4): 718–720, doi:10.1137/0210055
• 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
• Jensen, T. R.; Toft, B. (1995), Graph Coloring Problems, Wiley-Interscience, New York, ISBN 0-471-02865-7
• Khot, S. (2001), "Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring", Proc. 42nd Annual Symposium on Foundations of Computer Science, pp. 600–609, doi:10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3, S2CID 11987483
• Knuth, Donald Ervin (1997), Seminumerical Algorithms, The Art of Computer Programming, vol. 2 (3rd ed.), Reading/MA: Addison-Wesley, ISBN 0-201-89684-2
• Koivisto, Mikko (Jan 2004), Sum-Product Algorithms for the Analysis of Genetic Risks (Ph.D. thesis), Dept. CS Ser. Pub. A, vol. A-2004-1, University of Helsinki, ISBN 952-10-1578-0
• Kubale, M. (2004), Graph Colorings, American Mathematical Society, ISBN 0-8218-3458-4
• Kuhn, F. (2009), "Weak graph colorings: distributed algorithms and applications", Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures, pp. 138–144, doi:10.1145/1583991.1584032, ISBN 978-1-60558-606-9, S2CID 8857534
• Lawler, E.L. (1976), "A note on the complexity of the chromatic number problem", Information Processing Letters, 5 (3): 66–67, doi:10.1016/0020-0190(76)90065-X
• Leith, D.J.; Clifford, P. (2006), "A Self-Managed Distributed Channel Selection Algorithm for WLAN", Proc. RAWNET 2006, Boston, MA (PDF), retrieved 2016-03-03
• Lewis, R.M.R. (2016), A Guide to Graph Colouring: Algorithms and Applications, Springer International Publishing, ISBN 978-3-319-25728-0
• Linial, N. (1992), "Locality in distributed graph algorithms", SIAM Journal on Computing, 21 (1): 193–201, CiteSeerX 10.1.1.471.6378, doi:10.1137/0221015
• van Lint, J. H.; Wilson, R. M. (2001), A Course in Combinatorics (2nd ed.), Cambridge University Press, ISBN 0-521-80340-3
• Marx, Dániel (2004), "Graph colouring problems and their applications in scheduling", Periodica Polytechnica, Electrical Engineering, vol. 48, pp. 11–16, CiteSeerX 10.1.1.95.4268
• Mycielski, J. (1955), "Sur le coloriage des graphes" (PDF), Colloq. Math., 3 (2): 161–162, doi:10.4064/cm-3-2-161-162.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, hdl:10338.dmlcz/143192, ISBN 978-3-642-27874-7, MR 2920058.
• Panconesi, Alessandro; Rizzi, Romeo (2001), "Some simple distributed algorithms for sparse networks" (PDF), Distributed Computing, Berlin, New York: Springer-Verlag, 14 (2): 97–100, doi:10.1007/PL00008932, ISSN 0178-2770, S2CID 17661948
• Panconesi, A.; Srinivasan, A. (1996), "On the complexity of distributed network decomposition", Journal of Algorithms, vol. 20
• Sekine, K.; Imai, H.; Tani, S. (1995), "Computing the Tutte polynomial of a graph of moderate size", Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995), Lecture Notes in Computer Science, vol. 1004, Springer, pp. 224–233, doi:10.1007/BFb0015427, ISBN 3-540-60573-8
• Schneider, J. (2010), "A new technique for distributed symmetry breaking" (PDF), Proceedings of the Symposium on Principles of Distributed Computing
• Schneider, J. (2008), "A log-star distributed maximal independent set algorithm for growth-bounded graphs" (PDF), Proceedings of the Symposium on Principles of Distributed Computing
• Welsh, D. J. A.; Powell, M. B. (1967), "An upper bound for the chromatic number of a graph and its application to timetabling problems", The Computer Journal, 10 (1): 85–86, doi:10.1093/comjnl/10.1.85
• West, D. B. (1996), Introduction to Graph Theory, Prentice-Hall, ISBN 0-13-227828-6
• Wilf, H. S. (1986), Algorithms and Complexity, Prentice–Hall
• Yates, F. (1937), The design and analysis of factorial experiments (Technical Communication), vol. 35, Harpenden, England: Commonwealth Bureau of Soils
• Zuckerman, D. (2007), "Linear degree extractors and the inapproximability of Max Clique and Chromatic Number", Theory of Computing, 3: 103–128, doi:10.4086/toc.2007.v003a006
• Zykov, A. A. (1949), "О некоторых свойствах линейных комплексов" [On some properties of linear complexes], Mat. Sbornik, New Series (in русский), 24 (66): 163–188, MR 0035428. Translated into English in Amer. Math. Soc. Translation, 1952, MR0051516.

बाहरी संबंध

• High-Performance Graph Colouring Algorithms Suite of 8 different algorithms (implemented in C++) used in the book A Guide to Graph Colouring: Algorithms and Applications (Springer International Publishers, 2015).
• Graph Coloring Page by Joseph Culberson (graph coloring programs)
• CoLoRaTiOn by Jim Andrews and Mike Fellows is a graph coloring puzzle
• Links to Graph Coloring source codes
• Code for efficiently computing Tutte, Chromatic and Flow Polynomials Archived 2008-04-16 at the Wayback Machine by Gary Haggard, David J. Pearce and Gordon Royle
• A graph coloring Web App by Jose Antonio Martin H.