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