Oriented coloring
গ্রাফ তত্ত্বে, ওরিয়েন্টেড গ্রাফ কালারিং হল একটি বিশেষ ধরনের গ্রাফ কালারিং। অর্থাৎ, এটি একটি অভিযোজিত গ্রাফের শীর্ষে রঙের একটি বরাদ্দ যা সঠিকঃ কোনও দুটি সংলগ্ন শীর্ষ একই রঙ পায় না এবং ধারাবাহিকভাবে অভিযোজিত হয়ঃ যদি শীর্ষ এবং একই রঙ থাকে, এবং শীর্ষ এবং একই রঙ থাকে, তবে এবং উভয়ই গ্রাফের প্রান্ত হতে পারে না। সমতুল্যভাবে, একটি গ্রাফ জি-এর একটি ওরিয়েন্টেড গ্রাফ রঙ হল একটি ওরিয়েন্টেড গ্রাফ এইচ (যার শীর্ষগুলি রঙের প্রতিনিধিত্ব করে এবং যার চাপগুলি রঙের মধ্যে বৈধ ওরিয়েন্টেশনের প্রতিনিধিত্ব করে) যাতে জি থেকে এইচ পর্যন্ত সমরূপতা বিদ্যমান থাকে। একটি গ্রাফ জি-এর একটি ওরিয়েন্টেড ক্রোমাটিক সংখ্যা হল ওরিয়েন্টেড রঙে প্রয়োজনীয় সবচেয়ে কম রঙ; এটি সাধারণত দ্বারা চিহ্নিত করা হয়। একই সংজ্ঞা অনির্দিষ্ট গ্রাফগুলিতেও প্রসারিত করা যেতে পারে, একটি অনির্দিষ্ট গ্রাফের ওরিয়েন্টেড ক্রোমাটিক সংখ্যাকে তার যে কোনও ওরিয়েন্টেশনের বৃহত্তম ওরিয়েন্টেড ক্রোমাটিক সংখ্যা হিসাবে সংজ্ঞায়িত করে। উদাহরণ একটি নির্দেশিত 5-চক্রের ওরিয়েন্টেড ক্রোমাটিক সংখ্যা হল পাঁচটি। যদি চক্রটি চার বা তার কম রঙে রঙিন হয়, তবে দুটি সংলগ্ন শীর্ষে একই রঙ থাকে, অথবা দুটি শীর্ষে দুটি ধাপের ব্যবধানে একই রঙ থাকে। পরের ক্ষেত্রে, এই দুটি শীর্ষকে তাদের মধ্যবর্তী শীর্ষের সাথে সংযুক্তকারী প্রান্তগুলি অসঙ্গতিপূর্ণভাবে অভিমুখীঃ উভয়েরই একই জোড়া রঙ রয়েছে তবে বিপরীত অভিমুখ রয়েছে। সুতরাং, চার বা তার কম রঙের কোনও রঙ সম্ভব নয়। যাইহোক, প্রতিটি শীর্ষকে তার নিজস্ব অনন্য রঙ দেওয়া একটি বৈধ ভিত্তিক রঙের দিকে পরিচালিত করে। বৈশিষ্ট্য একটি অভিমুখী রঙ শুধুমাত্র একটি নির্দেশিত গ্রাফের জন্য বিদ্যমান থাকতে পারে যার কোনও লুপ বা নির্দেশিত 2-চক্র নেই। কারণ, একটি লুপের শেষ বিন্দুতে বিভিন্ন রঙ থাকতে পারে না এবং একটি 2-চক্রের উভয় প্রান্ত একই দুটি রঙের মধ্যে ধারাবাহিকভাবে অভিমুখী হতে পারে না। যদি এই শর্তগুলি পূরণ হয়, তবে সর্বদা একটি ভিত্তিক রঙ বিদ্যমান থাকে, উদাহরণস্বরূপ রঙ যা প্রতিটি শীর্ষে একটি ভিন্ন রঙ বরাদ্দ করে। যদি একটি ওরিয়েন্টেড রঙ সম্পূর্ণ হয়, এই অর্থে যে কোনও দুটি রঙ একত্রিত করে কম রঙের রঙ তৈরি করা যায় না, তবে এটি একটি টুর্নামেন্টে গ্রাফের সমরূপতার সাথে অনন্যভাবে মিলে যায়। টুর্নামেন্টে রঙের প্রতিটি রঙের জন্য একটি করে শীর্ষবিন্দু রয়েছে। প্রতিটি জোড়া রঙের জন্য, রঙিন গ্রাফে একটি প্রান্ত থাকে যার শেষ বিন্দুতে সেই দুটি রঙ থাকে, যা দুটি রঙের সাথে সামঞ্জস্যপূর্ণ শীর্ষগুলির মধ্যে টুর্নামেন্টের প্রান্তে তার অভিযোজন দেয়। অসম্পূর্ণ রঙগুলি টুর্নামেন্টে সমরূপতা দ্বারাও প্রতিনিধিত্ব করা যেতে পারে তবে এই ক্ষেত্রে রঙ এবং সমরূপতার মধ্যে যোগাযোগ এক-থেকে-এক নয়। বাউন্ডেড জেনাস, বাউন্ডেড ডিগ্রি বা বাউন্ডেড অ্যাসাইক্লিক ক্রোমাটিক নম্বরের অনির্দিষ্ট গ্রাফগুলিতেও বাউন্ডেড ওরিয়েন্টেড ক্রোমাটিক নম্বর রয়েছে। আরও দেখুন সোপেনা ওরিয়েন্টেড গ্রাফ কালারিং সম্পর্কে একটি সমীক্ষা পত্র লিখেছেন। ওরিয়েন্টেড কালারিং পেজ (সোপেনা দ্বারা পরিচালিত) রেফারেন্স গ্রাফ কালারিং