ग्रीडी कलरिंग

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

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

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

ग्रीडी कलरिंग की विविधताएं ऑनलाइन एल्गोरिदम में रंगों का चयन करती हैं, रेखांकऩ के बिना रंग वाले हिस्से की संरचना के बारे में कोई जानकारी के बिना, या रंगों की कुल संख्या को कम करने के लिए पहले उपलब्ध रंगों की तुलना में अन्य रंगों का चयन करें। ग्रीडी कलरिंग एल्गोरिदम को शेड्यूलिंग और पंजीकरण आवंटन समस्याओं, संयोजी खेलों के विश्लेषण और रंग और डिग्री के बीच संबंध पर ब्रूक्स के प्रमेय सहित अन्य गणितीय परिणामों के प्रमाणों के लिए लागू किया गया है। ग्रीडी कलरिंगों से व्युत्पन्न रेखांकन सिद्धांत में अन्य अवधारणाओं में एक रेखांकन की ग्रंडी संख्या (ग्रीडी कलरिंग द्वारा पाए जाने वाले रंगों की सबसे बड़ी संख्या), और अच्छे रंग वाले रेखांकन सम्मिलित हैं, जिनके लिए सभी ग्रीडी रंग एक ही संख्या का उपयोग करते हैं।

कलन विधि

किसी दिए गए शीर्ष क्रम के लिए ग्रीडी कलरिंग की गणना एल्गोरिथ्म द्वारा की जा सकती है जो रैखिक समय में चलता है। एल्गोरिथम, दिए गए क्रम में शीर्षों को संसाधित करता है, संसाधित होने पर प्रत्येक को एक रंग प्रदान करता है। रंगों को संख्याओं द्वारा दर्शाया जा सकता है $0,1,2,\dots$ और प्रत्येक शीर्ष को सबसे छोटी संख्या के साथ रंग दिया जाता है जो पहले से ही अपने पड़ोसियों में से एक द्वारा उपयोग नहीं किया जाता है सबसे छोटा उपलब्ध रंग खोजने के लिए, प्रत्येक रंग के पड़ोसियों की संख्या की गणना करने के लिए एक सरणी का उपयोग कर सकता है (या वैकल्पिक रूप से, पड़ोसियों के रंग के सेट का प्रतिनिधित्व करने के लिए), पायथन (प्रोग्रामिंग भाषा) में, एल्गोरिथ्म को इस प्रकार व्यक्त किया जा सकता है:

def first_available(color_list):
    """Return smallest non-negative integer not in the given list of colors."""
    color_set = set(color_list)
    count = 0
    while True:
        if count not in color_set:
            return count
        count += 1
        
def greedy_color(G, order):
    """Find the greedy coloring of G in the given order.
    The representation of G is assumed to be like https://www.python.org/doc/essays/graphs/
    in allowing neighbors of a node/vertex to be iterated over by "for w in G[node]".
    The return value is a dictionary mapping vertices to their colors."""
    color = dict()
    for node in order:
        used_neighbour_colors = [color[nbr] for nbr in G[node]
                                 if nbr in color]
        color[node] = first_available(used_neighbour_colors)
    return color

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

वैकल्पिक एल्गोरिद्म, समान रंग उत्पन्न करता है, प्रत्येक रंग, एक समय में एक रंग के साथ कोने के सेट को चुनने के लिए है। इस विधि में, प्रत्येक रंग वर्ग $C$ दिए गए क्रम में कोने के माध्यम से स्कैन करके चुना जाता है। जब यह स्कैन बेतार कशेरुक से मिलता है $v$ जिसका कोई पड़ोसी नहीं है $C$, यह जोड़ता है $v$ को $C$. इस प्रकार से, $C$ शीर्षों के बीच एक अधिकतम स्वतंत्र सेट बन जाता है जो पहले से ही छोटे रंग आवंटित नहीं किए गए थे। एल्गोरिथ्म बार-बार इस तरह से रंग वर्ग पाता है जब तक कि सभी कोने रंग नहीं होते। हालांकि, इसमें प्रत्येक रंग वर्ग के लिए रेखांकन के कई स्कैन, एक स्कैन बनाने के बजाय, ऊपर उल्लिखित पद्धति के बजाय, जो केवल एक स्कैन का उपयोग करता है।

क्रम करने का विकल्प

रेखांकन के कोने के विभिन्न क्रमांकन ग्रीडी कलरिंग के विभिन्न संख्याओं का उपयोग करने का कारण बन सकते हैं, रंग की इष्टतम संख्या से लेकर, कुछ मामलों में, रंग की एक संख्या जो रेखांकन में कोने की संख्या के आनुपातिक है। उदाहरण के लिए, एक क्राउन रेखांकन (दो अलग-अलग सेटों से बना एक रेखांकन n/2 शिखर {a₁, a₂, ...} और {b₁, b₂, ...} संयुक्त करके a_i को b_j जब कभी भी i ≠ j) ग्रीडी कलरिंग के लिए विशेष रूप से बुरा मामला हो सकता है। कशेरुक के a₁, b₁, a₂, b₂, ..., क्रम के साथ ग्रीडी कलरिंग n/2 रंग, का उपयोग करेगा, प्रत्येक जोड़ी (a_i, b_i). के लिए एक रंग। हालाँकि, इस रेखांकन के लिए रंगों की इष्टतम संख्या दो है, शीर्षों के लिए एक रंग a_i और दूसरा शिखरों के लिए b_i. वहाँ भी रेखांकन सम्मिलित हैं कि उच्च संभावना के साथ एक यादृच्छिक रूप से चुने गए शीर्ष क्रम न्यूनतम से बहुत बड़े कई रंगों की ओर ले जाता है। इसलिए, ग्रीडी कलरिंग में यह कुछ महत्व रखता है कि शीर्ष क्रम को सावधानी से चुनते हैं।

अच्छा क्रम

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

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

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

खराब क्रम

Main article: ग्रुंडी संख्या

किसी दिए गए रेखांकन के सबसे खराब क्रम के लिए ग्रीडी कलरिंग द्वारा उत्पादित रंगों की संख्या को उसकी ग्रंडी संख्या कहा जाता है। जैसा कि ग्रीडी रंग के लिए एक अच्छे शीर्ष क्रम का पता लगाना मुश्किल है, इसलिए एक बुरा शीर्ष क्रम खोज रहा है। किसी दिए गए रेखांकन के लिए यह निर्धारित करने के लिए एनपी-पूर्ण है G और संख्या k, क्या के शीर्षों का क्रम सम्मिलित है G जो ग्रीडी एल्गोरिथम का उपयोग करने का कारण बनता है k या अधिक रंग। विशेष रूप से, इसका मतलब यह है कि सबसे खराब क्रम खोजना मुश्किल है G.

रेखांकन जिसके लिए क्रम अप्रासंगिक है

Main article: अच्छे रंग का ग्राफ

अच्छे रंग के रेखांकन वे रेखांकन हैं जिनके लिए सभी शीर्ष क्रमांकन रंगों की एक ही संख्या का उत्पादन करते हैं। इन रेखांकन में, दोनों रंगीन संख्या और ग्रंडी संख्या के बराबर है। इनमें कोरेखांकन सम्मिलित हैं, जो वास्तव में ऐसे रेखांकऩ हैं जिनमें सभी प्रेरित सबरेखांकन अच्छी तरह से रंगे हुए हैं। हालांकि, यह निर्धारित करने के लिए सह-एनपी-पूर्ण है कि कोई रेखांकन अच्छी तरह से रंगा हुआ है या नहीं है।

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

पतितता

The triangular prism and square antiprism, graphs whose greedy colorings using the degeneracy ordering give larger-than-optimal numbers of colors

क्योंकि इष्टतम कोने क्रम खोजना मुश्किल है, अनुमानी का उपयोग किया गया है जो रंगों की इष्टतम संख्या की गारंटी न देते हुए रंगों की संख्या को कम करने का प्रयास करता है। ग्रीडी कलरिंग के लिए सामान्य रूप से उपयोग किया जाने वाला क्रम न्यूनतम डिग्री (रेखांकन सिद्धांत) के एक शीर्ष v का चयन करने के लिए है, v को पुनरावर्तन (कंप्यूटर विज्ञान), रूप से हटा दिया गया, और फिर क्रम में v को अंतिम स्थान दें। हटाए गए शीर्ष की सबसे बड़ी डिग्री जो इस एल्गोरिथम का सामना करती है, उसे रेखांकऩ का डीजेनरेसी (रेखांकऩ सिद्धांत) कहा जाता है, जिसे निरूपित किया जाता है d. ग्रीडी कलरिंग के संदर्भ में, उसी क्रम की रणनीति को सबसे छोटा अंतिम क्रम भी कहा जाता है। यह कोने क्रमिंग, और अध: पतन, रैखिक समय में गणना की जा सकती है। इसे पहले के कोने क्रमिंग मेथड के बेहतर संस्करण के रूप में देखा जा सकता है, जो सबसे बड़ा-पहला क्रमिंग है, जो वर्टिकल को उनके डिग्रियों द्वारा अवरोही क्रम में सॉर्ट करता है। अध: पतन क्रम के साथ, ग्रीडी कलरिंग अधिक से अधिक उपयोग करेंगे d + 1 रंग की। ऐसा इसलिए है, क्योंकि रंगीन होने पर, प्रत्येक शीर्ष में अधिकतम होगा d पहले से ही रंगीन पड़ोसी, इसलिए सबसे पहले में से एक d + 1 रंग इसके उपयोग के लिए निःशुल्क होंगे। अध: पतन क्रम के साथ ग्रीडी कलरिंग पेड़ों, छद्म वनों और मुकुट रेखांकन सहित रेखांकन के कुछ वर्गों के लिए इष्टतम रंग पा सकते हैं। मार्कोसियन,, गैसपेरियन & रीड (1996) एक रेखांकन परिभाषित करें $G$ होना $\beta$-बिल्कुल सही अगर, के लिए $G$ और हर प्रेरित सबरेखांकन $G$, रंगीन संख्या अध: पतन प्लस एक के बराबर होती है। इन रेखांकन के लिए, अध: पतन क्रम के साथ ग्रीडी एल्गोरिथ्म हमेशा इष्टतम होता है। प्रत्येक $\beta$-परफेक्ट रेखांकऩ एक सम-छिद्र-मुक्त रेखांकऩ होना चाहिए, क्योंकि यहां तक ​​कि चक्रों में रंगीन संख्या दो और अध: पतन दो होते हैं, जो परिभाषा में समानता से मेल नहीं खाते $\beta$- सही रेखांकन। यदि एक रेखांकऩ और उसका पूरक रेखांकऩ दोनों सम-छिद्र-मुक्त हैं, तो वे दोनों हैं $\beta$-उत्तम। रेखांकन जो दोनों सही रेखांकन हैं और $\beta$-परिपूर्ण रेखांकन बिलकुल तारकीय रेखांकन होते हैं। सम-छिद्र-मुक्त रेखांकऩ पर अधिक सामान्यतः पर, अध: पतन क्रम इष्टतम रंग को रंगों की इष्टतम संख्या के अधिकतम दोगुने के भीतर अनुमानित करता है; अर्थात्, इसका सन्निकटन अनुपात 2 है। यूनिट डिस्क रेखांकऩ पर इसका सन्निकटन अनुपात 3 है। त्रिकोणीय प्रिज्म सबसे छोटा रेखांकऩ है जिसके लिए इसकी एक डिजेनरेसी क्रमिंग एक गैर-इष्टतम रंग की ओर ले जाती है, और स्क्वायर एंटीप्रिज्म सबसे छोटा रेखांकऩ है जिसे इसके किसी भी अधःपतन क्रमिंग का उपयोग करके बेहतर ढंग से रंगा नहीं जा सकता है।

अनुकूली क्रम

ब्रेंज़ (1979) ने ग्रीडी कलरिंग में शीर्ष क्रम के लिए डीसैट नामक एक रणनीति का प्रस्ताव किया है जो रंग प्रक्रिया के साथ क्रमिंग के निर्माण को इंटरलीव करती है। ग्रीडी कलरिंग एल्गोरिथ्म के अपने संस्करण में, प्रत्येक चरण में रंग करने के लिए अगला शीर्ष अपने पड़ोस (रेखांकन सिद्धांत) में सबसे बड़ी संख्या के साथ एक के रूप में चुना जाता है। संबंधों के मामले में, अक्षत कोनेेस के उप-ग्राफ में अधिकतम डिग्री के एक शीर्ष को बंधित शीर्ष से चुना जाता है। हर कदम पर आस-पास के रंगों और उनके कार्डिनल के सेटों का ट्रैक रखने के द्वारा, इस विधि को रैखिक समय में लागू करना संभव है। यह विधि द्विदलीय रेखांकन के लिए इष्टतम रंग खोज सकती है, सभी कैक्टस रेखांकऩ, सभी पहिया रेखांकन ़, सभी रेखांकऩ ज़्यादा से ज़्यादा छह शीर्षों पर, और लगभग हर $k$-रंगीन रेखांकन। यद्यपि लेवेक & मफ़्रे (2005) ने मूल रूप से दावा किया था कि यह विधि मेयनियल रेखांकन के लिए इष्टतम रंग खोजती है, बाद में उन्हें इस दावे के लिए प्रति उदाहरण मिला है।।

वैकल्पिक रंग चयन योजनाएं

ग्रीडी कलरिंग एल्गोरिथ्म की विविधताओं को परिभाषित करना संभव है जिसमें दिए गए रेखांकन के कोने दिए गए क्रम में रंगीन होते हैं लेकिन जिसमें प्रत्येक शीर्ष के लिए चुना गया रंग आवश्यक रूप से पहला उपलब्ध रंग नहीं होता है। इनमें ऐसी विधियाँ सम्मिलित हैं जिनमें रेखांकऩ का बिना रंग वाला हिस्सा एल्गोरिथम के लिए अज्ञात है, या जिसमें एल्गोरिथम को बुनियादी ग्रीडी एल्गोरिथम की तुलना में बेहतर रंग विकल्प बनाने के लिए कुछ स्वतंत्रता दी जाती है।

ऑनलाइन चयन

ऑनलाइन एल्गोरिदम के ढांचे के भीतर वैकल्पिक रंग चयन रणनीतियों का अध्ययन किया गया है। ऑनलाइन रेखांकऩ-रंग समस्या में, रेखांकऩ के शीर्षों को एक रंग एल्गोरिथम के मनमाने क्रम में एक समय में एक के बाद एक प्रस्तुत किया जाता है; एल्गोरिथम को प्रत्येक शीर्ष के लिए एक रंग का चयन करना चाहिए, केवल पहले से संसाधित शीर्षों के बीच के रंगों और आसन्नताओं के आधार पर। इस संदर्भ में, एक रंग चयन रणनीति की गुणवत्ता को उसके प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिथम) द्वारा मापा जाता है, इसके द्वारा उपयोग किए जाने वाले रंगों की संख्या और दिए गए रेखांकन के लिए रंगों की इष्टतम संख्या के बीच का अनुपात है।

यदि रेखांकऩ पर कोई अतिरिक्त प्रतिबंध नहीं दिया गया है, तो इष्टतम प्रतिस्पर्धी अनुपात केवल थोड़ा उपरैखिक है। हालांकि, अंतराल रेखांकन के लिए, एक निरंतर प्रतिस्पर्धी अनुपात संभव है, जबकि द्विदलीय रेखांकन और विरल रेखांकन के लिए एक लघुगणकीय अनुपात प्राप्त किया जा सकता है। दरअसल, विरल रेखांकन के लिए, पहले उपलब्ध रंग को चुनने की मानक ग्रीडी कलरिंग रणनीति इस प्रतिस्पर्धी अनुपात को प्राप्त करती है, और किसी भी ऑनलाइन रंग एल्गोरिथ्म के प्रतिस्पर्धी अनुपात पर एक मिलान कम सीमा साबित करना संभव है।

पारसीमोनस रंग

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

अनुप्रयोग

क्योंकि यह तेज़ है और कई मामलों में कुछ रंगों का उपयोग कर सकता है, ग्रीडी कलरिंग का उपयोग उन अनुप्रयोगों में किया जा सकता है जहाँ एक अच्छे लेकिन इष्टतम रेखांकऩ रंग की आवश्यकता नहीं है। ग्रीडी एल्गोरिथ्म के प्रारंभिक अनुप्रयोगों में से एक पाठ्यक्रम शेड्यूलिंग जैसी समस्याओं के लिए था, जिसमें कार्यों का संग्रह समय स्लॉट के दिए गए सेट को सौंपा जाना चाहिए, एक ही समय स्लॉट के लिए असाइन किए जा रहे असंगत कार्यों से बचने। इसका उपयोग रजिस्टर आवंटन के लिए संकलक्स में भी किया जा सकता है, इसे एक रेखांकन पर लागू करके जिसका शिखर रजिस्टरों को असाइन किए जाने वाले मानों का प्रतिनिधित्व करता है और जिनके किनारे दो मानों के बीच संघर्ष का प्रतिनिधित्व करते हैं जिन्हें एक ही रजिस्टर में असाइन नहीं किया जा सकता है। कई मामलों में, ये हस्तक्षेप रेखांकन कॉर्डल रेखांकन हैं, जो ग्रीडी रंग को एक इष्टतम रजिस्टर असाइनमेंट का उत्पादन करने की अनुमति देते हैं।

संयोजी खेल सिद्धांत में, एक निष्पक्ष खेल के लिए एक निर्देशित विश्वकोश रेखांकन के रूप में स्पष्ट रूप में दिया गया है, जिसका शिखर खेल की स्थिति का प्रतिनिधित्व करता है और जिसके किनारे एक स्थिति से दूसरे स्थान पर वैध चाल का प्रतिनिधित्व करते हैं, ग्रीडी कलरिंग एल्गोरिथ्म (रेखांकन के एक सांस्थितिक क्रम के विपरीत का उपयोग करके) ) प्रत्येक स्थिति के निम-मूल्य की गणना करता है। इन मूल्यों का उपयोग किसी भी एकल खेल में इष्टतम खेल या खेलों के किसी भी अव्यवस्थित योग को निर्धारित करने के लिए किया जा सकता है। अधिकतम डिग्री के रेखांकन के लिए Δ, कोई भी ग्रीडी कलरिंग अधिक से अधिक उपयोग करेगा Δ + 1 रंग की। ब्रूक्स प्रमेय बताता है कि अधिकतम दो अपवादों (पूर्ण रेखांकन और चक्र रेखांकन) के साथ Δ रंगों की जरूरत है। ब्रूक्स के प्रमेय के एक प्रमाण में शीर्ष क्रम को खोजना सम्मिलित है जिसमें पहले दो शीर्ष अंतिम शीर्ष के निकट हैं लेकिन एक दूसरे के निकट नहीं हैं, और पिछले एक के अलावा प्रत्येक शीर्ष में कम से कम एक बाद का पड़ोसी है। इस संपत्ति के साथ एक क्रम देने के लिए, ग्रीडी कलरिंग एल्गोरिथ्म का सबसे अधिक उपयोग किया जाता है Δ रंग की है।।

संदर्भ

• Brélaz, Daniel (April 1979), "New methods to color the vertices of a graph", Communications of the ACM, 22 (4): 251–256, doi:10.1145/359094.359101
• Christen, Claude A.; Selkow, Stanley M. (1979), "Some perfect coloring properties of graphs", Journal of Combinatorial Theory, Series B, 27 (1): 49–59, doi:10.1016/0095-8956(79)90067-4, MR 0539075
• Chvátal, Václav (1984), "Perfectly orderable graphs", in Berge, Claude; Chvátal, Václav (eds.), Topics in Perfect Graphs, Annals of Discrete Mathematics, vol. 21, Amsterdam: North-Holland, pp. 63–68. As cited by Maffray (2003).
• Erdős, P.; Hare, W. R.; Hedetniemi, S. T.; Laskar, R. (1987), "On the equality of the Grundy and ochromatic numbers of a graph" (PDF), Journal of Graph Theory, 11 (2): 157–159, doi:10.1002/jgt.3190110205, MR 0889347.
• Frieze, Alan; McDiarmid, Colin (1997), "Algorithmic theory of random graphs", Random Structures & Algorithms, 10 (1–2): 5–42, doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.3.CO;2-6, MR 1611517.
• Gräf, A.; Stumpf, M.; Weißenfels, G. (1998), "On coloring unit disk graphs", Algorithmica, 20 (3): 277–293, doi:10.1007/PL00009196, MR 1489033.
• Hoàng, Chinh T.; Sritharan, R. (2016), "Chapter 28. Perfect Graphs", in Thulasiraman, Krishnaiyan; Arumugam, Subramanian; Brandstädt, Andreas; Nishizeki, Takao (eds.), Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, Chapman & Hall/CRC Computer and Information Science Series, vol. 34, CRC Press, pp. 707–750, ISBN 9781420011074.
• Husfeldt, Thore (2015), "Graph colouring algorithms", in Beineke, Lowell W.; Wilson, Robin J. (eds.), Topics in Chromatic Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 156, Cambridge University Press, pp. 277–303, arXiv:1505.05825, MR 3380176
• Irani, Sandy (1994), "Coloring inductive graphs on-line", Algorithmica, 11 (1): 53–72, doi:10.1007/BF01294263, MR 1247988.
• Janczewski, R.; Kubale, M.; Manuszewski, K.; Piwakowski, K. (2001), "The smallest hard-to-color graph for algorithm DSATUR", Discrete Mathematics, 236 (1–3): 151–165, doi:10.1016/S0012-365X(00)00439-8, MR 1830607.
• Kierstead, H. A.; Trotter, W. T. (1981), "An extremal problem in recursive combinatorics", Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II (Baton Rouge, La., 1981), Congressus Numerantium, 33: 143–153, MR 0681909. As cited by Irani (1994).
• Kosowski, Adrian; Manuszewski, Krzysztof (2004), "Classical coloring of graphs", in Kubale, Marek (ed.), Graph Colorings, Contemporary Mathematics, vol. 352, Providence, Rhode Island: American Mathematical Society, pp. 1–19, doi:10.1090/conm/352/06369, MR 2076987
• Kučera, Luděk (1991), "The greedy coloring is a bad probabilistic algorithm", Journal of Algorithms, 12 (4): 674–684, doi:10.1016/0196-6774(91)90040-6, MR 1130323.
• Johnson, David S. (1974), "Worst case behavior of graph coloring algorithms", Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974), Congressus Numerantium, vol. X, Winnipeg, Manitoba: Utilitas Math., pp. 513–527, MR 0389644.
• Lévêque, Benjamin; Maffray, Frédéric (October 2005), "Coloring Meyniel graphs in linear time" (PDF), in Raspaud, André; Delmas, Olivier (eds.), 7th International Colloquium on Graph Theory (ICGT '05), 12–16 September 2005, Hyeres, France, Electronic Notes in Discrete Mathematics, vol. 22, Elsevier, pp. 25–28, arXiv:cs/0405059, doi:10.1016/j.endm.2005.06.005. See also Lévêque, Benjamin; Maffray, Frédéric (January 9, 2006), Erratum : MCColor is not optimal on Meyniel graphs, arXiv:cs/0405059.
• Lovász, L. (1975), "Three short proofs in graph theory", Journal of Combinatorial Theory, Series B, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1, MR 0396344.
• Lovász, L.; Saks, M. E.; Trotter, W. T. (1989), "An on-line graph coloring algorithm with sublinear performance ratio", Discrete Mathematics, 75 (1–3): 319–325, doi:10.1016/0012-365X(89)90096-4, MR 1001404.
• Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A.; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, vol. 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1, MR 1952983.
• Markossian, S. E.; Gasparian, G. S.; Reed, B. A. (1996), "β-perfect graphs", Journal of Combinatorial Theory, Series B, 67 (1): 1–11, doi:10.1006/jctb.1996.0030, MR 1385380.
• Matula, David W. (1968), "A min-max theorem for graphs with application to graph coloring", SIAM 1968 National Meeting, SIAM Review, 10 (4): 481–482, doi:10.1137/1010115.
• Matula, David W.; Beck, L. L. (1983), "Smallest-last ordering and clustering and graph coloring algorithms", Journal of the ACM, 30 (3): 417–427, doi:10.1145/2402.322385, MR 0709826.
• Middendorf, Matthias; Pfeiffer, Frank (1990), "On the complexity of recognizing perfectly orderable graphs", Discrete Mathematics, 80 (3): 327–333, doi:10.1016/0012-365X(90)90251-C, MR 1049253.
• Mitchem, John (1976), "On various algorithms for estimating the chromatic number of a graph", The Computer Journal, 19 (2): 182–183, doi:10.1093/comjnl/19.2.182, MR 0437376.
• Nivasch, Gabriel (2006), "The Sprague–Grundy function of the game Euclid", Discrete Mathematics, 306 (21): 2798–2800, doi:10.1016/j.disc.2006.04.020, MR 2264378.
• Pereira, Fernando Magno Quintão; Palsberg, Jens (2005), "Register allocation via coloring of chordal graphs", in Yi, Kwangkeun (ed.), Programming Languages and Systems: Third Asian Symposium, APLAS 2005, Tsukuba, Japan, November 2–5, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3780, Springer, pp. 315–329, doi:10.1007/11575467_21
• Poletto, Massimiliano; Sarkar, Vivek (September 1999), "Linear scan register allocation", ACM Transactions on Programming Languages and Systems, 21 (5): 895–913, doi:10.1145/330249.330250.
• Rose, D.; Lueker, George; Tarjan, Robert E. (1976), "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing, 5 (2): 266–283, doi:10.1137/0205021, MR 0408312.
• Simmons, Gustavus J. (1982), "The ordered chromatic number of planar maps", Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congressus Numerantium, 36: 59–67, MR 0726050
• Sysło, Maciej M. (1989), "Sequential coloring versus Welsh–Powell bound", Discrete Mathematics, 74 (1–2): 241–243, doi:10.1016/0012-365X(89)90212-4, MR 0989136.
• Szekeres, George; Wilf, Herbert S. (1968), "An inequality for the chromatic number of a graph", Journal of Combinatorial Theory, 4: 1–3, doi:10.1016/S0021-9800(68)80081-X.
• Vishwanathan, Sundar (1992), "Randomized online graph coloring", Journal of Algorithms, 13 (4): 657–669, doi:10.1016/0196-6774(92)90061-G, MR 1187207.
• 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.
• Zaker, Manouchehr (2006), "Results on the Grundy chromatic number of graphs", Discrete Mathematics, 306 (2–3): 3166–3173, doi:10.1016/j.disc.2005.06.044, MR 2273147.