Scheinerman's conjecture
গণিতে, শাইনারম্যানের অনুমান, যা এখন একটি উপপাদ্য, বলে যে প্রতিটি সমতলীয় গ্রাফ সমতলে রেখাখন্ডের একটি সেটের ছেদ গ্রাফ। এই অনুমানটি ই. আর. শাইনারম্যান তাঁর পিএইচ. ডি থিসিসে (1984) প্রণয়ন করেছিলেন, পূর্ববর্তী ফলাফলগুলি অনুসরণ করে যে প্রতিটি সমতলীয় গ্রাফকে সমতলে সহজ বক্ররেখার একটি সেটের ছেদ গ্রাফ হিসাবে উপস্থাপন করা যেতে পারে। দ্বারা প্রমাণিত হয়। উদাহরণস্বরূপ, নীচে বাম দিকে দেখানো গ্রাফ জি-কে নীচে ডানদিকে দেখানো অংশগুলির সেটের ছেদ গ্রাফ হিসাবে উপস্থাপন করা যেতে পারে। এখানে, জি-এর শীর্ষগুলি সরলরেখার অংশ দ্বারা প্রতিনিধিত্ব করা হয় এবং জি-এর প্রান্তগুলি ছেদ বিন্দু দ্বারা প্রতিনিধিত্ব করা হয়। শাইনারম্যান আরও অনুমান করেছিলেন যে মাত্র তিনটি দিক সহ বিভাগগুলি 3-রঙিন গ্রাফের প্রতিনিধিত্ব করার জন্য যথেষ্ট হবে এবং অনুমান করেছিলেন যে অনুরূপভাবে প্রতিটি সমতলীয় গ্রাফকে চারটি দিক ব্যবহার করে উপস্থাপন করা যেতে পারে। যদি একটি গ্রাফ শুধুমাত্র কে দিকনির্দেশযুক্ত বিভাগগুলির সাথে প্রতিনিধিত্ব করা হয় এবং কোনও দুটি বিভাগ একই রেখার অন্তর্গত না হয়, তবে গ্রাফটি কে রঙ ব্যবহার করে রঙ করা যেতে পারে, প্রতিটি দিকের জন্য একটি রঙ। অতএব, যদি প্রতিটি সমতলীয় গ্রাফকে কেবল চারটি দিক দিয়ে এইভাবে উপস্থাপন করা যায়, তবে চার রঙের উপপাদ্যটি অনুসরণ করে। এবং প্রমাণ করেছেন যে প্রতিটি দ্বিদলীয় সমতলীয় গ্রাফকে অনুভূমিক এবং উল্লম্ব রেখা বিভাগের ছেদ গ্রাফ হিসাবে উপস্থাপন করা যেতে পারে; এই ফলাফলের জন্য আরও দেখুন। প্রমাণ করে যে প্রতিটি ত্রিভুজ-মুক্ত সমতলীয় গ্রাফকে শুধুমাত্র তিনটি দিকের রেখাখন্ডের ছেদ গ্রাফ হিসাবে উপস্থাপন করা যেতে পারে; এই ফলাফল গ্রটজশের উপপাদ্যকে বোঝায় যে ত্রিভুজ-মুক্ত সমতলীয় গ্রাফগুলি তিনটি রঙ দিয়ে রঙ করা যেতে পারে। এটি প্রমাণ করে যে, যদি একটি সমতলীয় গ্রাফ জি-কে এমনভাবে 4-রঙের করা যায় যে কোনও পৃথক চক্র চারটি রঙই ব্যবহার করে না, তবে জি-এর অংশগুলির ছেদ গ্রাফ হিসাবে একটি উপস্থাপনা রয়েছে। প্রমাণ করে যে সমতলীয় গ্রাফগুলি 1-স্ট্রিং-এ রয়েছে, সমতলে সাধারণ বক্ররেখার ছেদ গ্রাফের শ্রেণী যা প্রতি জোড়ায় সর্বাধিক একটি ক্রসিং পয়েন্টে একে অপরকে ছেদ করে। এই শ্রেণীটি শাইনারম্যানের অনুমানে প্রদর্শিত অংশগুলির ছেদ গ্রাফ এবং এরলিচ এট আল-এর ফলাফল থেকে অনিয়ন্ত্রিত সহজ বক্ররেখার ছেদ গ্রাফের মধ্যে মধ্যবর্তী। এটিকে বৃত্ত প্যাকিং উপপাদ্যের সাধারণীকরণ হিসাবেও দেখা যেতে পারে, যা একটি স্পর্শকের মধ্যে বক্ররেখা ছেদ করার অনুমতি দিলে একই ফলাফল দেখায়। এই অনুমানের প্রমাণ এই ফলাফলের উন্নতির উপর ভিত্তি করে তৈরি হয়েছিল। রেফারেন্স। । । । । । । । । । । প্ল্যানার গ্রাফস অনুমান যা প্রমাণিত হয়েছে