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