ग्राफ कलरिंग: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (8 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Methodic assignment of colors to elements of a graph}} | {{Short description|Methodic assignment of colors to elements of a graph}} | ||
[[File:Petersen graph 3-coloring.svg|thumb|right|3 रंगों के साथ [[पीटरसन ग्राफ]] का उचित शीर्ष रंग, न्यूनतम संभव संख्या।]]ग्राफ़ सिद्धांत में, ग्राफ़ कलरिंग [[ग्राफ लेबलिंग]] का एक विशेष | [[File:Petersen graph 3-coloring.svg|thumb|right|3 रंगों के साथ [[पीटरसन ग्राफ]] का उचित शीर्ष रंग, न्यूनतम संभव संख्या।]]ग्राफ़ सिद्धांत में, '''ग्राफ़ कलरिंग''' [[ग्राफ लेबलिंग]] का एक विशेष स्थिति है; यह कुछ बाधाओं के अधीन एक ग्राफ के तत्वों के लिए पारंपरिक रूप से "रंग" कहे जाने वाले लेबल का एक असाइनमेंट है। अपने सरलतम रूप में, यह ग्राफ के शीर्षों को इस प्रकार रंगने का एक तरीका है कि कोई भी दो आसन्न शीर्ष एक ही रंग के न हों; इसे वर्टेक्स कलरिंग कहा जाता है। इसी तरह, किनारे का रंग प्रत्येक किनारे को एक रंग प्रदान करता है ताकि कोई भी दो आसन्न किनारे एक ही रंग के न हों, और समतल ग्राफ का एक चेहरा रंग प्रत्येक चेहरे या क्षेत्र को एक रंग प्रदान करता है ताकि कोई भी दो आसन्न किनारे एक ही रंग के चेहरे न हों एक ही रंग का न हो। | ||
वर्टेक्स कलरिंग का उपयोग प्रायः ग्राफ कलरिंग की समस्याओं को पेश करने के लिए किया जाता है, क्योंकि अन्य कलरिंग समस्याओं को वर्टेक्स कलरिंग इंस्टेंस में बदला जा सकता है। उदाहरण के लिए, एक ग्राफ़ का एक किनारा रंग उसके लाइन ग्राफ़ का सिर्फ एक शीर्ष रंग है, और एक समतल ग्राफ़ का एक चेहरा रंग उसके दोहरे का सिर्फ एक शीर्ष रंग है। हालांकि, गैर-शीर्ष रंग की समस्याओं को प्रायः कहा जाता है और उनका अध्ययन किया जाता है। यह आंशिक रूप से शैक्षणिक है, और आंशिक रूप से क्योंकि कुछ समस्याओं का उनके गैर-शीर्ष रूप में सबसे अच्छा अध्ययन किया जाता है, जैसा कि किनारे के रंग के | वर्टेक्स कलरिंग का उपयोग प्रायः ग्राफ कलरिंग की समस्याओं को पेश करने के लिए किया जाता है, क्योंकि अन्य कलरिंग समस्याओं को वर्टेक्स कलरिंग इंस्टेंस में बदला जा सकता है। उदाहरण के लिए, एक ग्राफ़ का एक किनारा रंग उसके लाइन ग्राफ़ का सिर्फ एक शीर्ष रंग है, और एक समतल ग्राफ़ का एक चेहरा रंग उसके दोहरे का सिर्फ एक शीर्ष रंग है। हालांकि, गैर-शीर्ष रंग की समस्याओं को प्रायः कहा जाता है और उनका अध्ययन किया जाता है। यह आंशिक रूप से शैक्षणिक है, और आंशिक रूप से क्योंकि कुछ समस्याओं का उनके गैर-शीर्ष रूप में सबसे अच्छा अध्ययन किया जाता है, जैसा कि किनारे के रंग के स्थिति में है। | ||
रंगों का उपयोग करने की परिपाटी एक मानचित्र के देशों को रंगने से उत्पन्न होती है, जहाँ प्रत्येक चेहरा सचमुच रंगीन होता है। यह | रंगों का उपयोग करने की परिपाटी एक मानचित्र के देशों को रंगने से उत्पन्न होती है, जहाँ प्रत्येक चेहरा सचमुच रंगीन होता है। यह सतह में अंतर्निहितग्राफ के चेहरों को रंगने के लिए सामान्यीकृत किया गया था। प्लेनर द्वैत द्वारा यह कोने को रंगने लगा, और इस रूप में यह सभी रेखांकन के लिए सामान्य हो गया। गणितीय और कंप्यूटर अभ्यावेदन में, पहले कुछ धनात्मक या गैर-ऋणात्मक पूर्णांकों को "रंग" के रूप में उपयोग करना विशिष्ट है। सामान्य तौर पर, कोई भी परिमित सेट को "रंग सेट" के रूप में उपयोग कर सकता है। रंजक समस्या की प्रकृति रंगों की संख्या पर निर्भर करती है न कि वे क्या हैं। | ||
ग्राफ़ कलरिंग कई व्यावहारिक अनुप्रयोगों के साथ-साथ सैद्धांतिक चुनौतियों का भी आनंद लेती है। शास्त्रीय प्रकार की समस्याओं के अलावा, ग्राफ़ पर, या जिस तरह से एक रंग सौंपा गया है, या यहाँ तक कि स्वयं रंग पर भी विभिन्न सीमाएँ निर्धारित की जा सकती हैं। यहां तक कि यह लोकप्रिय संख्या पहेली सुडोकू के रूप में साधारण जनता के बीच लोकप्रियता तक पहुंच गया है। ग्राफ कलरिंग अभी भी अनुसंधान का एक बहुत ही सक्रिय क्षेत्र है। | ग्राफ़ कलरिंग कई व्यावहारिक अनुप्रयोगों के साथ-साथ सैद्धांतिक चुनौतियों का भी आनंद लेती है। शास्त्रीय प्रकार की समस्याओं के अलावा, ग्राफ़ पर, या जिस तरह से एक रंग सौंपा गया है, या यहाँ तक कि स्वयं रंग पर भी विभिन्न सीमाएँ निर्धारित की जा सकती हैं। यहां तक कि यह लोकप्रिय संख्या पहेली सुडोकू के रूप में साधारण जनता के बीच लोकप्रियता तक पहुंच गया है। ग्राफ कलरिंग अभी भी अनुसंधान का एक बहुत ही सक्रिय क्षेत्र है। | ||
| Line 13: | Line 13: | ||
{{See also |चार रंग प्रमेय का इतिहास|ग्राफ सिद्धांत का इतिहास}} | {{See also |चार रंग प्रमेय का इतिहास|ग्राफ सिद्धांत का इतिहास}} | ||
ग्राफ़ कलरिंग के बारे में पहला परिणाम नक्शों के रंग के रूप में लगभग अनन्य रूप से प्लानर ग्राफ़ से संबंधित है। इंग्लैंड की काउंटियों के मानचित्र को रंगने की | ग्राफ़ कलरिंग के बारे में पहला परिणाम नक्शों के रंग के रूप में लगभग अनन्य रूप से प्लानर ग्राफ़ से संबंधित है। इंग्लैंड की काउंटियों के मानचित्र को रंगने की प्रयास करते समय, [[फ्रांसिस गुथरी]] ने चार रंगों के अनुमान को स्वीकार किया, यह देखते हुए कि चार रंग नक्शे को रंगने के लिए पर्याप्त थे ताकि किसी भी क्षेत्र में एक समान सीमा साझा करने पर एक ही रंग न हो। गुथरी के भाई ने [[यूनिवर्सिटी कॉलेज लंदन|यूनिवर्सिटी कॉलेज]] में उनके गणित के शिक्षक [[ऑगस्टस डी मॉर्गन]] को प्रश्न दिया, जिन्होंने 1852 में [[विलियम रोवन हैमिल्टन]] को लिखे एक पत्र में इसका उल्लेख किया। [[आर्थर केली]] ने 1879 में लंदन मैथमेटिकल सोसाइटी की बैठक में समस्या को उठाया। उसी वर्ष, [[अल्फ्रेड केम्पे]] ने एक पेपर प्रकाशित किया जिसमें परिणाम स्थापित करने का दावा किया गया था, और एक दशक तक चार-रंग की समस्या हल हो गई थी। उनकी उपलब्धि के लिए केम्पे को रॉयल सोसाइटी का फेलो और बाद में लंदन मैथमेटिकल सोसाइटी का अध्यक्ष चुना गया था।<ref>M. Kubale, ''History of graph coloring'', in {{harvtxt|Kubale|2004}}</ref> | ||
1890 में हेवुड ने बताया कि केम्पे का तर्क गलत था। हालांकि, उस पेपर में उन्होंने यह कहते हुए पांच रंग प्रमेय को साबित कर दिया कि केम्पे के विचारों का उपयोग करके प्रत्येक प्लानर मानचित्र को पांच से अधिक रंगों से रंगा जा सकता है। अगली शताब्दी में, रंगों की संख्या को चार तक कम करने के लिए बड़ी मात्रा में काम और सिद्धांत विकसित किया गया था, जब तक कि केनेथ एपेल और वोल्फगैंग हेइकेन द्वारा 1976 में चार रंग प्रमेय को अंततः सिद्ध नहीं किया गया था। साक्ष्य हेवुड और केम्पे के विचारों पर वापस चले गए और बड़े पैमाने पर हस्तक्षेपों के विकास की अवहेलना की। | 1890 में हेवुड ने बताया कि केम्पे का तर्क गलत था। हालांकि, उस पेपर में उन्होंने यह कहते हुए पांच रंग प्रमेय को साबित कर दिया कि केम्पे के विचारों का उपयोग करके प्रत्येक प्लानर मानचित्र को पांच से अधिक रंगों से रंगा जा सकता है। अगली शताब्दी में, रंगों की संख्या को चार तक कम करने के लिए बड़ी मात्रा में काम और सिद्धांत विकसित किया गया था, जब तक कि केनेथ एपेल और वोल्फगैंग हेइकेन द्वारा 1976 में चार रंग प्रमेय को अंततः सिद्ध नहीं किया गया था। साक्ष्य हेवुड और केम्पे के विचारों पर वापस चले गए और बड़े पैमाने पर हस्तक्षेपों के विकास की अवहेलना की।<ref>{{harvtxt|van Lint|Wilson|2001|loc=Chap. 33}}</ref> चार रंग प्रमेय का प्रमाण पहला प्रमुख कंप्यूटर-एडेड प्रमाण होने के लिए भी उल्लेखनीय है। | ||
1912 में, [[जॉर्ज डेविड बिरखॉफ]] ने रंगीन समस्याओं का अध्ययन करने के लिए रंगीन बहुपदों की प्रारम्भ की, जिन्हें टुट्टे से टुट्टे बहुपदों तक सामान्यीकृत किया गया था, [[बीजगणितीय ग्राफ सिद्धांत]] में महत्वपूर्ण संरचनाएं। केम्पे ने पहले ही 1879 में सामान्य, गैर-प्लानर | 1912 में, [[जॉर्ज डेविड बिरखॉफ]] ने रंगीन समस्याओं का अध्ययन करने के लिए रंगीन बहुपदों की प्रारम्भ की, जिन्हें टुट्टे से टुट्टे बहुपदों तक सामान्यीकृत किया गया था, [[बीजगणितीय ग्राफ सिद्धांत]] में महत्वपूर्ण संरचनाएं। केम्पे ने पहले ही 1879 में सामान्य, गैर-प्लानर स्थिति पर ध्यान आकर्षित किया था, <ref>{{harvtxt|Jensen|Toft|1995}}, p. 2</ref> और 20 वीं शताब्दी की प्रारम्भ में उच्च क्रम सतहों के लिए प्लानर ग्राफ रंग के सामान्यीकरण पर कई परिणाम दिखाई दिए। | ||
1960 में, क्लॉड बर्ज ने ग्राफ कलरिंग के बारे में एक और अनुमान तैयार किया, मजबूत सही ग्राफ अनुमान, जो मूल रूप से एक सूचना-सैद्धांतिक अवधारणा से प्रेरित था जिसे शैनन द्वारा प्रस्तुत ग्राफ की शून्य-त्रुटि क्षमता कहा जाता है। यह अनुमान 40 वर्षों तक अनसुलझा रहा, जब तक कि इसे 2002 में [[मारिया चुडनोव्स्की|चुडनोव्स्की]], [[नील रॉबर्टसन (गणितज्ञ)|नील रॉबर्टसन]], सीमोर और थॉमस द्वारा एक प्रसिद्ध मजबूत पूर्ण ग्राफ प्रमेय के रूप में स्थापित नहीं किया | 1960 में, क्लॉड बर्ज ने ग्राफ कलरिंग के बारे में एक और अनुमान तैयार किया, मजबूत सही ग्राफ अनुमान, जो मूल रूप से एक सूचना-सैद्धांतिक अवधारणा से प्रेरित था जिसे शैनन द्वारा प्रस्तुत ग्राफ की शून्य-त्रुटि क्षमता कहा जाता है। यह अनुमान 40 वर्षों तक अनसुलझा रहा, जब तक कि इसे 2002 में [[मारिया चुडनोव्स्की|चुडनोव्स्की]], [[नील रॉबर्टसन (गणितज्ञ)|नील रॉबर्टसन]], सीमोर और थॉमस द्वारा एक प्रसिद्ध मजबूत पूर्ण ग्राफ प्रमेय के रूप में स्थापित नहीं किया गया था। | ||
1970 के दशक की प्रारम्भ से ग्राफ कलरिंग का एक एल्गोरिथम समस्या के रूप में अध्ययन किया गया है: क्रोमैटिक नंबर प्रॉब्लम (नीचे देखें) 1972 से कार्प की 21 | 1970 के दशक की प्रारम्भ से ग्राफ कलरिंग का एक एल्गोरिथम समस्या के रूप में अध्ययन किया गया है: क्रोमैटिक नंबर प्रॉब्लम (नीचे देखें) 1972 से कार्प की 21 एनपी-सम्पूर्ण समस्याओं में से एक है, और लगभग उसी समय बैकट्रैकिंग घातीय-समय एल्गोरिथम पर आधारित विभिन्न तरीके थे और ज़ीकोव (1949) के विलोपन-संकुचन पुनरावृत्ति पर। ग्राफ कलरिंग के प्रमुख अनुप्रयोगों में से एक, कंपाइलर्स में रजिस्टर आवंटन, 1981 में पेश किया गया था। | ||
== परिभाषा और शब्दावली == | == परिभाषा और शब्दावली == | ||
| Line 30: | Line 30: | ||
जब बिना किसी योग्यता के उपयोग किया जाता है, तो ग्राफ़ का रंग लगभग हमेशा एक ''उचित शीर्ष रंग'' होता है, अर्थात् ग्राफ़ के शीर्षों को रंगों के साथ लेबल करना, जैसे कि एक ही किनारे (ग्राफ़ सिद्धांत) को साझा करने वाले दो शीर्षों का रंग समान नहीं होता है। चूंकि एक [[पाश (ग्राफ सिद्धांत)]] (अर्थात् सीधे अपने आप में एक कनेक्शन) के साथ एक शीर्ष कभी भी ठीक से रंगीन नहीं हो सकता है, यह समझा जाता है कि इस संदर्भ में ग्राफ लूपलेस हैं। | जब बिना किसी योग्यता के उपयोग किया जाता है, तो ग्राफ़ का रंग लगभग हमेशा एक ''उचित शीर्ष रंग'' होता है, अर्थात् ग्राफ़ के शीर्षों को रंगों के साथ लेबल करना, जैसे कि एक ही किनारे (ग्राफ़ सिद्धांत) को साझा करने वाले दो शीर्षों का रंग समान नहीं होता है। चूंकि एक [[पाश (ग्राफ सिद्धांत)]] (अर्थात् सीधे अपने आप में एक कनेक्शन) के साथ एक शीर्ष कभी भी ठीक से रंगीन नहीं हो सकता है, यह समझा जाता है कि इस संदर्भ में ग्राफ लूपलेस हैं। | ||
वर्टेक्स लेबल्स के लिए ''रंगों'' का उपयोग करने की शब्दावली मैप कलरिंग पर वापस जाती है। ''लाल'' और ''नीला'' जैसे लेबल केवल तभी उपयोग किए जाते हैं जब रंगों की संख्या कम होती है, और सामान्यतः यह समझा जाता है कि लेबल [[पूर्णांक]] | वर्टेक्स लेबल्स के लिए ''रंगों'' का उपयोग करने की शब्दावली मैप कलरिंग पर वापस जाती है। ''लाल'' और ''नीला'' जैसे लेबल केवल तभी उपयोग किए जाते हैं जब रंगों की संख्या कम होती है, और सामान्यतः यह समझा जाता है कि लेबल [[पूर्णांक]] से खींचे गए हैं {{math|{1, 2, 3, …}.}} अधिक से अधिक उपयोग करने वाला रंग {{mvar|k}} रंग कहा जाता है (उचित) {{mvar|k}}-रंग। किसी ग्राफ़ को रंगने के लिए आवश्यक रंगों की न्यूनतम संख्या {{mvar|G}} इसकी रंगीन संख्या कहा जाता है, और इसे प्रायः निरूपित किया जाता है {{math|χ(''G'')}}. कभी-कभी {{math|γ(''G'')}} उपयोग किया जाता है, क्योंकि {{math|χ(''G'')}} ग्राफ की [[यूलर विशेषता]] को निरूपित करने के लिए भी प्रयोग किया जाता है। एक ग्राफ जिसे असाइन किया जा सकता है (उचित) {{mvar|k}}-रंग है {{mvar|k}}-रंगीन, और यह है{{mvar|k}}-क्रोमैटिक अगर इसकी क्रोमैटिक संख्या बिल्कुल है {{mvar|k}}. एक ही रंग को सौंपे गए शीर्षों के एक उपसमुच्चय को रंग वर्ग कहा जाता है, ऐसा प्रत्येक वर्ग एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) बनाता है। इस प्रकार, एक {{mvar|k}}-coloring एक शीर्ष सेट को {{mvar|k}}-स्वतंत्र सेटों में विभाजित करने के बराबर है, और {{mvar|k}}-match और {{mvar|k}}-colourable शब्दों का अर्थ समान है। | ||
=== रंगीन बहुपद === | === रंगीन बहुपद === | ||
| Line 45: | Line 45: | ||
| 0 || 0 || 12 || 72 || … | | 0 || 0 || 12 || 72 || … | ||
|} | |} | ||
रंगीन बहुपद एक कार्य है {{math|''P''(''G'',''t'')}} जो की संख्या की गणना करता है {{mvar|t}}- का रंग {{mvar|G}}. जैसा कि नाम इंगित करता है, दिए गए के लिए {{mvar|G}} | रंगीन बहुपद एक कार्य है {{math|''P''(''G'',''t'')}} जो की संख्या की गणना करता है {{mvar|t}}- का रंग {{mvar|G}}. जैसा कि नाम इंगित करता है, दिए गए के लिए {{mvar|G}} फंक्शन वास्तव में एक [[बहुपद]] है {{mvar|t}}. उदाहरण ग्राफ के लिए, {{math|1=''P''(''G'',''t'') = ''t''(''t'' – 1){{sup|2}}(''t'' – 2)}}, वास्तव में {{math|1=''P''(''G'',4) = 72}}. | ||
रंगीन बहुपद में की रंगीनता के बारे में अधिक जानकारी सम्मिलित है {{mvar|G}} रंगीन संख्या की तुलना में। वास्तव में, {{mvar|χ}} सबसे छोटा | रंगीन बहुपद में की रंगीनता के बारे में अधिक जानकारी सम्मिलित है {{mvar|G}} रंगीन संख्या की तुलना में। वास्तव में, {{mvar|χ}} सबसे छोटा धनात्मक पूर्णांक है जो {{math|1=χ(''G'') = min{''k'' : ''P''(''G'',''k'') > 0}.}}रंगीन बहुपद का शून्य नहीं है | ||
{| class="wikitable" style="background:white;" | {| class="wikitable" style="background:white;" | ||
| Line 70: | Line 70: | ||
===किनारे का रंग === | ===किनारे का रंग === | ||
{{Main|किनारे का रंग}} | {{Main|किनारे का रंग}} | ||
एक ग्राफ़ का एक किनारा रंग ''किनारों'' का एक उचित रंग है, जिसका अर्थ है कि किनारों को रंगों का एक असाइनमेंट ताकि एक ही रंग के दो किनारों पर कोई शीर्ष घटना न हो। एक किनारे का रंग {{mvar|k}} रंगों को कहा जाता है {{mvar|k}}-एज-कलरिंग और एज सेट को विभाजित करने की समस्या के बराबर है {{mvar|k}} [[मिलान (ग्राफ सिद्धांत)]]। किसी ग्राफ़ के किनारों को रंगने के लिए आवश्यक रंगों की सबसे छोटी संख्या {{mvar|G}} क्रोमैटिक | एक ग्राफ़ का एक किनारा रंग ''किनारों'' का एक उचित रंग है, जिसका अर्थ है कि किनारों को रंगों का एक असाइनमेंट ताकि एक ही रंग के दो किनारों पर कोई शीर्ष घटना न हो। एक किनारे का रंग {{mvar|k}} रंगों को कहा जाता है {{mvar|k}}-एज-कलरिंग और एज सेट को विभाजित करने की समस्या के बराबर है {{mvar|k}} [[मिलान (ग्राफ सिद्धांत)]]। किसी ग्राफ़ के किनारों को रंगने के लिए आवश्यक रंगों की सबसे छोटी संख्या {{mvar|G}} क्रोमैटिक सूचकांक या एज क्रोमैटिक नंबर है, {{math|χ′(''G'')}}. टैट कलरिंग [[क्यूबिक ग्राफ]] का 3-किनारे वाला कलरिंग है। [[चार रंग प्रमेय]] इस दावे के बराबर है कि प्रत्येक प्लानर क्यूबिक [[पुल (ग्राफ सिद्धांत)]] ग्राफ एक टैट रंग को स्वीकार करता है। | ||
=== कुल रंग === | === कुल रंग === | ||
| Line 77: | Line 77: | ||
=== बिना लेबल वाला रंग === | === बिना लेबल वाला रंग === | ||
किसी ग्राफ़ का लेबल रहित रंग ग्राफ़ के [[ग्राफ ऑटोमोर्फिज्म]] की क्रिया के अंतर्गत किसी रंग की [[समूह क्रिया (गणित)]] है। ध्यान दें कि रंग लेबल रहते हैं; यह वह ग्राफ है जिसे लेबल नहीं किया गया है। | किसी ग्राफ़ का लेबल रहित रंग ग्राफ़ के [[ग्राफ ऑटोमोर्फिज्म]] की क्रिया के अंतर्गत किसी रंग की [[समूह क्रिया (गणित)]] है। ध्यान दें कि रंग लेबल रहते हैं; यह वह ग्राफ है जिसे लेबल नहीं किया गया है। रंगीन बहुपद का एक एनालॉग है जो किसी दिए गए परिमित रंग सेट से ग्राफ के बिना लेबल वाले रंगों की संख्या की गणना करता है। अगर हम एक ग्राफ के रंग की व्याख्या करते हैं {{mvar|d}} में एक वेक्टर के रूप में शिखर {{tmath|\mathbb{Z}^d}}, ऑटोमोर्फिज्म की क्रिया रंगीन वेक्टर में गुणांकों का क्रम [[परिवर्तन]] है। | ||
रंगीन बहुपद का एक एनालॉग है जो किसी दिए गए परिमित रंग सेट से ग्राफ के बिना लेबल वाले रंगों की संख्या की गणना करता है। | |||
अगर हम एक ग्राफ के रंग की व्याख्या करते हैं {{mvar|d}} में एक वेक्टर के रूप में शिखर {{tmath|\mathbb{Z}^d}}, ऑटोमोर्फिज्म की क्रिया रंगीन वेक्टर में गुणांकों का क्रम [[परिवर्तन]] है। | |||
== गुण == | == गुण == | ||
| Line 89: | Line 86: | ||
: <math>1 \le \chi(G) \le n.</math> | : <math>1 \le \chi(G) \le n.</math> | ||
एकमात्र ग्राफ़ जो 1-रंग का हो सकता है, वे [[किनारा रहित ग्राफ]] हैं। एक [[पूरा ग्राफ]] <math>K_n</math> n शीर्षों की आवश्यकता है <math>\chi(K_n)=n</math> रंग की। एक इष्टतम रंग में रंग वर्गों की प्रत्येक जोड़ी के बीच ग्राफ के | एकमात्र ग्राफ़ जो 1-रंग का हो सकता है, वे [[किनारा रहित ग्राफ]] हैं। एक [[पूरा ग्राफ]] <math>K_n</math> n शीर्षों की आवश्यकता है <math>\chi(K_n)=n</math> रंग की। एक इष्टतम रंग में रंग वर्गों की प्रत्येक जोड़ी के बीच ग्राफ के m किनारों में से कम से कम एक होना चाहिए, इसलिए | ||
: <math>\chi(G)(\chi(G)-1) \le 2m.</math> | : <math>\chi(G)(\chi(G)-1) \le 2m.</math> | ||
| Line 97: | Line 94: | ||
सही रेखांकन के लिए यह सीमा तंग है। क्लिक्स ढूँढना क्लिक्स समस्या के रूप में जाना जाता है। | सही रेखांकन के लिए यह सीमा तंग है। क्लिक्स ढूँढना क्लिक्स समस्या के रूप में जाना जाता है। | ||
अधिक सामान्यतः एक परिवार <math>\mathcal{F}</math> रेखांकन का Χ-बाध्य है<math>\chi</math>-बाउंडेड अगर कोई फंक्शन है <math>c</math> जैसे कि रेखांकन <math>G</math> में <math>\mathcal{F}</math> ज्यादा से ज्यादा रंगा जा सकता है <math>c(\omega(G))</math> रंग, सही रेखांकन | अधिक सामान्यतः एक परिवार <math>\mathcal{F}</math> रेखांकन का Χ-बाध्य है<math>\chi</math>-बाउंडेड अगर कोई फंक्शन है <math>c</math> जैसे कि रेखांकन <math>G</math> में <math>\mathcal{F}</math> ज्यादा से ज्यादा रंगा जा सकता है <math>c(\omega(G))</math> रंग, सही रेखांकन <math>c(\omega(G))=\omega(G)</math>के परिवार के लिए यह कार्य है . | ||
2-रंगीन ग्राफ़ वास्तव में द्विदलीय ग्राफ़ हैं, जिनमें वृक्ष (ग्राफ़ सिद्धांत) और वन सम्मिलित हैं। | 2-रंगीन ग्राफ़ वास्तव में द्विदलीय ग्राफ़ हैं, जिनमें वृक्ष (ग्राफ़ सिद्धांत) और वन सम्मिलित हैं। | ||
| Line 103: | Line 100: | ||
चार रंग प्रमेय के अनुसार, प्रत्येक प्लानर ग्राफ 4-रंगों का हो सकता है। | चार रंग प्रमेय के अनुसार, प्रत्येक प्लानर ग्राफ 4-रंगों का हो सकता है। | ||
एक [[लालची रंग]] दिखाता है कि प्रत्येक ग्राफ को अधिकतम शीर्ष [[डिग्री (ग्राफ सिद्धांत)]] की तुलना में एक और रंग से रंगा जा सकता है। | एक [[लालची रंग|लोभी रंग]] दिखाता है कि प्रत्येक ग्राफ को अधिकतम शीर्ष [[डिग्री (ग्राफ सिद्धांत)]] की तुलना में एक और रंग से रंगा जा सकता है। | ||
: <math>\chi(G) \le \Delta(G) + 1. </math> | : <math>\chi(G) \le \Delta(G) + 1. </math> | ||
पूरा रेखांकन है <math>\chi(G)=n</math> और <math>\Delta(G)=n-1</math>, और [[विषम चक्र]] हैं <math>\chi(G)=3</math> और <math>\Delta(G)=2</math>, इसलिए इन ग्राफ़ के लिए यह बाउंड सर्वोत्तम संभव है। अन्य सभी मामलों में, सीमा में थोड़ा सुधार किया जा सकता है; ब्रूक्स प्रमेय<ref>{{harvtxt|Brooks|1941}}</ref> बताता है | पूरा रेखांकन है <math>\chi(G)=n</math> और <math>\Delta(G)=n-1</math>, और [[विषम चक्र]] हैं <math>\chi(G)=3</math> और <math>\Delta(G)=2</math>, इसलिए इन ग्राफ़ के लिए यह बाउंड सर्वोत्तम संभव है। अन्य सभी मामलों में, सीमा में थोड़ा सुधार किया जा सकता है; ब्रूक्स प्रमेय<ref>{{harvtxt|Brooks|1941}}</ref> बताता है | ||
: ब्रूक्स प्रमेय:<math>\chi (G) \le \Delta (G) </math> एक जुड़े हुए, सरल ग्राफ़ G के लिए, जब तक कि G एक पूर्ण ग्राफ़ या विषम चक्र न हो। | : ब्रूक्स प्रमेय:<math>\chi (G) \le \Delta (G) </math> एक जुड़े हुए, सरल ग्राफ़ G के लिए, जब तक कि G एक पूर्ण ग्राफ़ या विषम चक्र न हो। | ||
| Line 117: | Line 115: | ||
: <math> \chi_H(G)\leq \chi(G).</math> | : <math> \chi_H(G)\leq \chi(G).</math> | ||
{{vanchor|वेक्टर रंगीन संख्या}}: होने देना <math>W</math> एक | {{vanchor|वेक्टर रंगीन संख्या}}: होने देना <math>W</math> एक धनात्मक अर्ध-निश्चित मैट्रिक्स हो जैसे कि <math> W_{i,j} \le -\tfrac{1}{k-1} </math> जब कभी भी <math>(i,j) </math> में बढ़त है <math>G</math> परिभाषित करना <math>\chi_V(G)</math> कम से कम k जिसके लिए <math>W</math> ऐसा मैट्रिक्स उपस्थित हो तब: | ||
: <math> \chi_V(G)\leq \chi(G).</math> | : <math> \chi_V(G)\leq \chi(G).</math> | ||
लोवाज़ संख्या: एक पूरक ग्राफ की लोवाज़ संख्या भी रंगीन संख्या पर एक निचली सीमा है: | |||
: <math> \vartheta(\bar{G}) \leq \chi(G).</math> | : <math> \vartheta(\bar{G}) \leq \chi(G).</math> | ||
भिन्नात्मक वर्णिक संख्या: किसी ग्राफ की भिन्नात्मक वर्णिक संख्या वर्णिक संख्या पर भी निचली सीमा होती है: | भिन्नात्मक वर्णिक संख्या: किसी ग्राफ की भिन्नात्मक वर्णिक संख्या वर्णिक संख्या पर भी निचली सीमा होती है: | ||
| Line 129: | Line 127: | ||
: प्रमेय ({{harvard citations|nb|first=William T.|last=Tutte|year=1947|author-link=W. T. Tutte}},<ref>{{citation | last = Descartes | first = Blanche | author-link = Blanche Descartes | journal = Eureka | title = A three colour problem | volume = 21 | date = April 1947}}</ref> {{harvard citations|nb|first=Alexander|last=Zykov|year=1949|author-link=Alexander Zykov}}, {{harvard citations|nb|first=Jan|last=Mycielski|year=1955|author-link=Jan Mycielski}}): मनमाने ढंग से उच्च रंग संख्या के साथ त्रिभुज-मुक्त ग्राफ़ उपस्थित हैं। | : प्रमेय ({{harvard citations|nb|first=William T.|last=Tutte|year=1947|author-link=W. T. Tutte}},<ref>{{citation | last = Descartes | first = Blanche | author-link = Blanche Descartes | journal = Eureka | title = A three colour problem | volume = 21 | date = April 1947}}</ref> {{harvard citations|nb|first=Alexander|last=Zykov|year=1949|author-link=Alexander Zykov}}, {{harvard citations|nb|first=Jan|last=Mycielski|year=1955|author-link=Jan Mycielski}}): मनमाने ढंग से उच्च रंग संख्या के साथ त्रिभुज-मुक्त ग्राफ़ उपस्थित हैं। | ||
यह साबित करने के लिए, माइसील्स्की और ज़्यकोव दोनों ने, प्रत्येक ने त्रिभुज-मुक्त ग्राफ़ के आगमनात्मक रूप से परिभाषित परिवार का निर्माण किया, लेकिन मनमाने ढंग से बड़ी रंगीन संख्या के साथ।<ref>{{citation | last1 = Scott | first1 = Alex | last2 = Seymour | first2 = Paul | journal = Journal of Graph Theory | pages = 2–3 | title = A survey of χ-boundedness | volume = 95 | year = 2020 | doi = 10.1002/jgt.22601 | issue = 3| s2cid = 4760027 }}.</ref> बर्लिंग (1965)<ref>{{citation | last = Burling | first = James Perkins | title = On coloring problems of families of prototypes (PhD thesis) | publisher = University of Colorado | location = Boulder | year = 1965}}.</ref> निर्मित अक्ष संरेखित बक्से में <math>\mathbb{R}^{3}</math> जिसका [[चौराहा ग्राफ]] त्रिभुज-मुक्त है और ठीक से रंगने के लिए मनमाने ढंग से कई रंगों की आवश्यकता होती है। ग्राफ़ के इस परिवार को बर्लिंग ग्राफ़ कहा जाता है। पावलिक एट अल द्वारा दिए गए | यह साबित करने के लिए, माइसील्स्की और ज़्यकोव दोनों ने, प्रत्येक ने त्रिभुज-मुक्त ग्राफ़ के आगमनात्मक रूप से परिभाषित परिवार का निर्माण किया, लेकिन मनमाने ढंग से बड़ी रंगीन संख्या के साथ।<ref>{{citation | last1 = Scott | first1 = Alex | last2 = Seymour | first2 = Paul | journal = Journal of Graph Theory | pages = 2–3 | title = A survey of χ-boundedness | volume = 95 | year = 2020 | doi = 10.1002/jgt.22601 | issue = 3| s2cid = 4760027 }}.</ref> बर्लिंग (1965)<ref>{{citation | last = Burling | first = James Perkins | title = On coloring problems of families of prototypes (PhD thesis) | publisher = University of Colorado | location = Boulder | year = 1965}}.</ref> निर्मित अक्ष संरेखित बक्से में <math>\mathbb{R}^{3}</math> जिसका [[चौराहा ग्राफ|प्रतिच्छेदन ग्राफ]] त्रिभुज-मुक्त है और ठीक से रंगने के लिए मनमाने ढंग से कई रंगों की आवश्यकता होती है। ग्राफ़ के इस परिवार को बर्लिंग ग्राफ़ कहा जाता है। पावलिक एट अल द्वारा दिए गए सतह में त्रिभुज-मुक्त रेखा खंडों के एक परिवार के निर्माण के लिए ग्राफ़ के समान वर्ग का उपयोग किया जाता है। (2014)।<ref name="Triangle-free intersection graphs o">{{citation | last1 = Pawlik | first1 = A. | last2 = Kozik | first2 = J. | last3 = Krawczyk | first3 = T. | last4 = Lasoń | first4 = M. | last5 = Micek | first5 = P. | last6 = Trotter | first6 = W. | last7 = Walczak | first7 = B. | journal = [[Journal of Combinatorial Theory]] | pages = 6–10 | title = Triangle-free intersection graphs of line segments with large chromatic number | series = Series B | volume = 105 | year = 2014 | doi = 10.1016/j.jctb.2013.11.001 | issue = 5| doi-access = free }}</ref> यह दर्शाता है कि इसके प्रतिच्छेदन ग्राफ की रंगीन संख्या भी मनमाने ढंग से बड़ी है। इसलिए, इसका तात्पर्य है कि अक्ष संरेखित बक्से में <math>\mathbb{R}^{3}</math> साथ ही लाइन सेगमेंट में <math>\mathbb{R}^{2}</math> χ-बाध्य नहीं हैं।<ref name="Triangle-free intersection graphs o"/> | ||
ब्रूक्स के प्रमेय से, उच्च रंगीन संख्या वाले ग्राफ़ में उच्च अधिकतम डिग्री होनी चाहिए। लेकिन रंगीनता पूरी तरह से स्थानीय घटना नहीं है: उच्च गर्थ (ग्राफ सिद्धांत) वाला एक ग्राफ स्थानीय रूप से पेड़ की तरह दिखता है, क्योंकि सभी चक्र लंबे होते हैं, लेकिन इसकी रंगीन संख्या 2 नहीं होनी चाहिए: | ब्रूक्स के प्रमेय से, उच्च रंगीन संख्या वाले ग्राफ़ में उच्च अधिकतम डिग्री होनी चाहिए। लेकिन रंगीनता पूरी तरह से स्थानीय घटना नहीं है: उच्च गर्थ (ग्राफ सिद्धांत) वाला एक ग्राफ स्थानीय रूप से पेड़ की तरह दिखता है, क्योंकि सभी चक्र लंबे होते हैं, लेकिन इसकी रंगीन संख्या 2 नहीं होनी चाहिए: | ||
: प्रमेय (पॉल एर्डोस | एर्डोस): मनमाने ढंग से उच्च परिधि और रंगीन संख्या के ग्राफ | : प्रमेय (पॉल एर्डोस | एर्डोस): मनमाने ढंग से उच्च परिधि और रंगीन संख्या के ग्राफ उपस्थित हैं।<ref>{{citation | last = Erdős | first = Paul | author-link = Paul Erdős | journal = Canadian Journal of Mathematics | pages = 34–38 | title = Graph theory and probability | volume = 11 | year = 1959 | doi = 10.4153/CJM-1959-003-9| s2cid = 122784453 }}.</ref> | ||
=== रंगीन सूचकांक पर सीमा === | === रंगीन सूचकांक पर सीमा === | ||
जी का किनारा रंग इसके लाइन ग्राफ का शीर्ष रंग है <math>L(G)</math>, और इसके | जी का किनारा रंग इसके लाइन ग्राफ का शीर्ष रंग है <math>L(G)</math>, और इसके विपरीत, इस प्रकार | ||
:<math>\chi'(G)=\chi(L(G)). </math> | :<math>\chi'(G)=\chi(L(G)). </math> | ||
| Line 156: | Line 154: | ||
[[अनंत ग्राफ]] कलरिंग के बारे में कुछ परिणामों में से दो निम्नलिखित हैं: | [[अनंत ग्राफ]] कलरिंग के बारे में कुछ परिणामों में से दो निम्नलिखित हैं: | ||
* यदि एक अनंत ग्राफ जी के सभी परिमित सबग्राफ के-रंगीन हैं, तो पसंद के स्वयंसिद्ध की धारणा के तहत जी भी है। यह डी ब्रुजन-एर्दोस प्रमेय (ग्राफ सिद्धांत) है | {{harvtxt|de Bruijn|Erdős|1951}}. | * यदि एक अनंत ग्राफ जी के सभी परिमित सबग्राफ के-रंगीन हैं, तो पसंद के स्वयंसिद्ध की धारणा के तहत जी भी है। यह डी ब्रुजन-एर्दोस प्रमेय (ग्राफ सिद्धांत) है | {{harvtxt|de Bruijn|Erdős|1951}}. | ||
*यदि कोई ग्राफ़ प्रत्येक n ≥ n के लिए पूर्ण n-रंग स्वीकार करता है | *यदि कोई ग्राफ़ प्रत्येक ''n'' ≥ ''n''<sub>0</sub> के लिए पूर्ण n-रंग स्वीकार करता है, यह एक अनंत पूर्ण रंग को स्वीकार करता है {{harv|Fawcett|1978}}. | ||
=== | === प्रारंभिक समस्याएं === | ||
जैसा कि ऊपर कहा, <math> \omega(G) \le \chi(G) \le \Delta(G) + 1. </math> 1998 से रीड का एक अनुमान यह है कि मूल्य अनिवार्य रूप से निचली सीमा के करीब है, | जैसा कि ऊपर कहा, <math> \omega(G) \le \chi(G) \le \Delta(G) + 1. </math> 1998 से रीड का एक अनुमान यह है कि मूल्य अनिवार्य रूप से निचली सीमा के करीब है, | ||
<math> \chi(G) \le \left\lceil \frac{\omega(G) + \Delta(G) + 1}{2} \right\rceil. </math> | <math> \chi(G) \le \left\lceil \frac{\omega(G) + \Delta(G) + 1}{2} \right\rceil. </math> | ||
| Line 220: | Line 218: | ||
}} | }} | ||
=== बहुपद समय === | === बहुपद समय === | ||
यह निर्धारित करना कि क्या एक ग्राफ को 2 रंगों से रंगा जा सकता है, यह निर्धारित करने के बराबर है कि क्या ग्राफ एक द्विदलीय ग्राफ है, और इस प्रकार रैखिक समय में या तो चौड़ाई- | यह निर्धारित करना कि क्या एक ग्राफ को 2 रंगों से रंगा जा सकता है, यह निर्धारित करने के बराबर है कि क्या ग्र | ||