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