Oriented coloring
گراف تھیوری میں، مبنی گراف کلرنگ گراف کلرنگ کی ایک خاص قسم ہے۔ یعنی، یہ ایک مبنی گراف کے عمودی حصوں پر رنگوں کی تفویض ہے جو مناسب ہے: کوئی بھی دو ملحقہ عمودی حصے ایک ہی رنگ کے نہیں ہوتے ہیں، اور مستقل طور پر مبنی ہوتے ہیں: اگر عمودی حصے اور ایک ہی رنگ کے ہوتے ہیں، اور عمودی حصے اور ایک ہی رنگ کے ہوتے ہیں، تو پھر اور دونوں گراف میں کنارے نہیں ہو سکتے۔ مساوی طور پر، گراف G کا مبنی گراف رنگ ایک مبنی گراف H ہے (جس کے عمودی حصے رنگوں کی نمائندگی کرتے ہیں اور جن کے آرکس رنگوں کے درمیان درست سمتوں کی نمائندگی کرتے ہیں) جیسے کہ G سے H تک ہومومورفزم موجود ہے۔ گراف G کا مبنی کرومیٹک نمبر ایک مبنی رنگ میں درکار سب سے کم رنگ ہے۔ اسے عام طور پر اس کے ذریعے ظاہر کیا جاتا ہے۔ اسی تعریف کو غیر ہدایت شدہ گرافوں تک بھی بڑھایا جا سکتا ہے، اس کے ساتھ ساتھ، کسی غیر ہدایت شدہ گراف کے مبنی کرومیٹک نمبر کو اس کی کسی بھی سمت کا سب سے بڑا مبنی کرومیٹک نمبر قرار دے کر۔ مثالیں ایک ڈائریکٹڈ 5 سائیکل کا اورینٹڈ کرومیٹک نمبر پانچ ہے۔ اگر سائیکل چار یا اس سے کم رنگوں سے رنگا ہوا ہے، تو یا تو دو ملحقہ عمودی ایک ہی رنگ کے ہوتے ہیں، یا دو عمودی دو قدم کے فاصلے پر ایک ہی رنگ کے ہوتے ہیں۔ مؤخر الذکر صورت میں، ان دونوں عمودی حصوں کو ان کے درمیان عمودی حصے سے جوڑنے والے کنارے متضاد طور پر مبنی ہوتے ہیں: دونوں میں رنگوں کی ایک ہی جوڑی ہوتی ہے لیکن مخالف سمتوں کے ساتھ۔ اس طرح، چار یا اس سے کم رنگوں کے ساتھ کوئی رنگ ممکن نہیں ہے۔ تاہم، ہر سرے کو اس کا اپنا منفرد رنگ دینے سے ایک درست مبنی رنگ نکلتا ہے۔ خصوصیات ایک مبنی رنگ صرف ایک ہدایت شدہ گراف کے لیے موجود ہو سکتا ہے جس میں کوئی لوپ یا ہدایت شدہ 2 سائیکل نہ ہوں۔ کیونکہ، ایک لوپ کے اختتامی نکات پر مختلف رنگ نہیں ہو سکتے، اور ایک 2-سائیکل کے دونوں کنارے ایک ہی دو رنگوں کے درمیان مستقل طور پر مبنی نہیں ہو سکتے۔ اگر ان شرائط کو پورا کیا جاتا ہے، تو ہمیشہ ایک مبنی رنگ موجود رہتا ہے، مثال کے طور پر وہ رنگ جو ہر سرے کو مختلف رنگ تفویض کرتا ہے۔ اگر ایک مبنی رنگ مکمل ہے، اس معنی میں کہ کم رنگوں کے ساتھ رنگ پیدا کرنے کے لیے کسی بھی دو رنگوں کو ضم نہیں کیا جا سکتا، تو یہ ٹورنامنٹ میں گراف ہومومورفزم سے منفرد طور پر مطابقت رکھتا ہے۔ ٹورنامنٹ میں رنگ میں ہر رنگ کے لیے ایک ورٹیکس ہوتا ہے۔ رنگوں کے ہر جوڑے کے لیے، رنگین گراف میں ایک کنارے ہوتا ہے جس کے اختتامی نکات پر وہ دو رنگ ہوتے ہیں، جو دو رنگوں سے مطابقت رکھنے والے عمودی حصوں کے درمیان ٹورنامنٹ میں کنارے پر اپنی سمت دیتا ہے۔ نامکمل رنگوں کی نمائندگی ٹورنامنٹ میں ہومومورفزم کے ذریعے بھی کی جا سکتی ہے لیکن اس صورت میں رنگوں اور ہومومورفزم کے درمیان خط و کتابت ون ٹو ون نہیں ہے۔ باؤنڈڈ جینس، باؤنڈڈ ڈگری، یا باؤنڈڈ ایسائکلک کرومیٹک نمبر کے غیر ہدایت شدہ گراف میں بھی باؤنڈڈ اورینٹڈ کرومیٹک نمبر ہوتے ہیں۔ یہ بھی دیکھیں کہ سوپینا نے مبنی گراف کلرنگ کے بارے میں ایک سروے پیپر لکھا۔ اورینٹڈ کلرنگ پیج (سوپینا کے زیر انتظام) حوالہ جات گراف کلرنگ