ہر نقشے لئی چار رنگ، لکیری ویلے وچ لبھے گئے

کسے پدھری شیٹ اُتے واہیا کوئی وی نقشہ چار رنگاں نال اینج رنگیا جا سکدا اے کہ گوانڈھی ملک کدی اک رنگ سانجھا نہ کرن۔ فرانسس گتھری (Francis Guthrie) نے 1852 وچ ایہدا قیاس کیتا؛ ایپل (Appel) تے ہیکن (Haken) نے 1976 وچ ایہنوں ثابت کیتا۔ پر مسئلہ اثباتی (theorem) صرف ایہہ آکھدا اے کہ چار رنگ موجود نیں۔ کسے دتے نقشے لئی اوہناں نوں کیویں لبھیئے؟ “کوئی سوکھا جواب نہیں،” یونیورسٹی آف ٹوکیو دے یوتا اینوئے (Yuta Inoue) تے جاپان، کینیڈا، سلووینیا تے ڈنمارک دے اوہناں دے پنج ساتھی لکھدے نیں۔ ایہہ اینا اُلجھیا ہویا رہیا اے کہ ایہدے نال کئی تجویز کردہ جوابی مثالاں (counterexamples) سامنے آئیاں۔

بِندو، لکیراں تے تکوناں

ہر ملک اک بِندو، یا ورٹیکس (vertex)، بن جاندا اے تے ہر سانجھی سرحد اک لکیر، یا ایج (edge): نقشہ اک پدھرا گراف (planar graph) بن جاندا اے، جو لکیراں نوں اک دوجے اُتوں لنگھائے بنا واہیا جاندا اے۔ ایہنوں رنگن دا مطلب اے ہر ورٹیکس نوں چار رنگاں وچوں اک دینا، ہر ایج دے دوہاں سریاں اُتے وکھرا۔ ورٹیکساں دی گنتی نوں n آکھو۔ تکون بندیاں (triangulations) نوں سانبھنا کافی اے، جتھے ہر پاسا اک تکون ہوندا اے: ودھ ایج رنگائی نوں صرف اوکھا کردے نیں۔

کیمپے دا وٹاندرا

بنیادی چال اے۔ بی۔ کیمپے (A. B. Kempe) دے 1879 دے اک مقالے توں آؤندی اے۔ چار رنگاں دے جوڑے بناؤ، مثلاً لال نال نیلا تے ہرا نال پیلا۔ اک کیمپے زنجیر (Kempe chain) ورٹیکساں دا اک جُڑیا ہویا ٹولہ اے جو اک جوڑے دے دو رنگ پاؤندا اے۔ اک پوری زنجیر اُتے اوہناں دو رنگاں نوں وٹان نال رنگائی ٹھیک رہندی اے۔

اک ورٹیکس v لؤ جیہدے چار گوانڈھی نیں، اوہدے دوالے ترتیب نال v0 توں v3، تے پہلاں باقی نوں رنگو۔ جے گوانڈھی تن یا گھٹ رنگ ورتدے نیں، تے v خالی رنگ لے لیندا اے۔ جے اوہ چارے ورتدے نیں، تے v0 توں شروع ہون والی زنجیر دا پچھا کرو جو v0 تے v2 دے رنگاں وچ اے۔ جے ایہہ v2 تیکر نہیں اپڑدی، تے ایہنوں وٹا دیو: v0، v2 دا رنگ لے لیندا اے، تے v لئی اک رنگ خالی ہو جاندا اے۔ جے ایہہ v2 تیکر اپڑ جاندی اے، تے ایہدی تھاں v1 دی زنجیر نوں v1 تے v3 دے رنگاں وچ وٹاؤ، تاں جے v1، v3 دا رنگ لے لوے۔

ٹکڑے جو ہمیشہ ٹھیک کیتے جا سکدے نیں

مسئلے دے ثبوت گھٹائے جا سکن والیاں بنتراں (reducible configurations) اُتے کھلوتے نیں: نکے نمونے جو کٹ کے کڈھے جا سکدے نیں، فیر باقی رنگے جان مگروں واپس رکھے جا سکدے نیں۔ جے اوہناں دے چھلے (ring) — یعنی اوہناں دے بالکل دوالے دے ورٹیکس — دے رنگ نہیں بہندے، تے باہر کیتیاں گئیاں کیمپے دیاں سدھار والیاں تبدیلیاں دی اک محدود گنتی اوہناں نوں ہمیشہ ٹھیک کر دیندی اے: ایتھے ورتے گئے نمونیاں لئی ودھ توں ودھ 25، جنہاں دے چھلیاں وچ ودھ توں ودھ 18 ورٹیکس نیں۔

اک گھٹائی جا سکن والی بنتر (کھبے؛ ہر نمبر دسدا اے کہ پورے نقشے وچ اوس ورٹیکس دے کِنے گوانڈھی ہونے لازمی نیں) تے اوہی نمونہ اپنے چھلے R نال پورا کیتا ہویا (سجے)۔ — شکل 1، Inoue et al. (2026)، arXiv:2610.39753۔

رابرٹسن، سینڈرز، سیمور تے تھامس (Robertson, Sanders, Seymour and Thomas) نے 1997 وچ وکھایا کہ ایس طرح، اک ویلے اک نمونہ، کیویں رنگیا جاوے۔ ہر گیڑا گراف نوں کجھ ورٹیکس نال نکا کردا اے تے پورے گراف اُتوں اک گیڑے دی قیمت لیندا اے، ایس لئی ویلا مربعی (quadratic) اے: دُگنے وڈے نقشے لئی چار گُنا لما۔

اک پچھلے مقالے (FOCS’26) وچ، اوہناں ای چھ لکھاریاں نے ثابت کیتا کہ ہر تکون بندی وچ n دے تناسب نال اک دوجے نوں نہ چھوہن والیاں گھٹائیاں جا سکن والیاں بنتراں ہوندیاں نیں، جو 8,202 دی اک لسٹ وچوں لئیاں جاندیاں نیں — یا اونے ای نکے چکر جنہاں دے دوہاں پاسے ورٹیکس ہون، جو وی مدد کردے نیں۔ اوہ سارے نمونے اکو واری کڈھدے نیں، باقی نوں رنگدے نیں، فیر سارے چھلے اکٹھے ٹھیک کردے نیں۔ کیمپے دی اک بے ترتیب تبدیلی کسے چھلے دی مدد کردی اے جے اوہ رنگاں دا ٹھیک جوڑا چُنے (تن وچوں اک موقع) تے چھلے نوں چھوہن والی ہر زنجیر اُتے ٹھیک ٹاس (ہر اک لئی دو وچوں اک موقع)۔ اجیہیاں 18 تیکر زنجیراں نال، ایہہ گھٹ توں گھٹ 3 × 2¹⁸ یعنی 786,432 وچوں اک موقع اے: نکا، پر پکا۔ ایس لئی گیڑیاں دی گنتی صرف log n وانگ ودھدی اے، لگ بھگ اونی واری جِنی واری n نوں ادھا کیتا جا سکدا اے۔ پر اک تبدیلی گراف دا اک پکا حصہ شامل کر سکدی اے: ہر اک دی قیمت اک پورا گیڑا اے، کُل n log n۔

گیڑے دی تھاں اک ٹیبل

نواں مقالہ log n تبدیلیاں رکھدا اے پر ہر اک نوں سستا کردا اے۔ n دے تناسب والے ویلے دی تیاری مگروں، ہر تبدیلی اوسطاً لگ بھگ n / log n قدماں وچ لبھی تے کیتی جاندی اے۔ فیر log n تبدیلیاں رل کے n دے تناسب والا ویلا لیندیاں نیں — لکیری ویلا (linear time) — اک حد جیہنوں لکھاری سب توں ودھیا (optimal) آکھدے نیں۔

چال “چار روسیاں دا طریقہ” (Method of Four Russians) اے۔ اک نکا مسئلہ جو ½ log n بِٹاں دے کوڈ وچ آ جاوے — n لکھن لئی لوڑیندے بائنری ہندسیاں دا ادھا — اوہدے ودھ توں ودھ √n ممکن روپ ہوندے نیں، ایس لئی اوہناں سبھناں دے جواب پہلاں ای گِن کے اک ٹیبل وچ سانبھے جا سکدے نیں۔ منیا گیا کمپیوٹر، جیہدے حافظے دے لفظ لگ بھگ log n بِٹ دے نیں، کوئی وی سانبھیا جواب اک قدم وچ پڑھ لیندا اے۔

گراف نوں واری واری، چھوٹیاں سرحداں والے اک دوجے اندر بنے علاقیاں وچ کٹیا جاندا اے۔ سب توں نکے لگ بھگ log n ورٹیکس رکھدے نیں تے، رنگاں سمیت، اک کوڈ وچ آ جاندے نیں۔ ہر علاقے لئی، اک نکا خلاصہ گراف درج کردا اے کہ سرحد دے کیہڑے ورٹیکس اک کیمپے زنجیر سانجھی کردے نیں۔ فیر اک تبدیلی “وٹاؤ” یا “رکھو” بِٹاں دیاں لڑیاں بن کے تھلے جاندی اے، تے ہر نکے علاقے وچ اک ویکھنی ہر رنگ نوں نواں کر دیندی اے۔

چار رنگاں نال رنگے گراف دا اک حصہ۔ سلیٹی تھاں اک علاقہ R اے؛ موٹے کالے ایج لال-نیلے تے ہرے-پیلے جوڑیاں دیاں کیمپے زنجیراں دے نیں۔ — شکل 2، Inoue et al. (2026)، arXiv:2610.39753۔

اوسے علاقے دا خلاصہ: ہر نیلا دھبہ کیمپے زنجیر دے اک ٹکڑے دی تھاں اے، تے اوہدیاں لکیراں دسدیاں نیں کہ اوہ سرحد دے کیہڑے ورٹیکس جوڑدا اے۔ — شکل 3، Inoue et al. (2026)، arXiv:2610.39753۔

پاسے سٹے بنا چُننا

بے ترتیب چوناں نال، ایہہ طریقہ پہلاں ای اوسطاً لکیری ویلے وچ نقشہ رنگ دیندا اے۔ رفتار گوائے بنا پاسیاں نوں کڈھنا “سب توں کِتے ودھ اوکھا حصہ” سی۔ اک چھلے نوں جیوندا آکھو جدوں تیکر ہُن تیکر دا ہر فیصلہ اوہدے حق وچ گیا ہووے۔ جے اوہنوں چھوہن والیاں u اَن فیصلہ زنجیراں ٹاس اُتے چھڈ دتیاں جاندیاں، تے اوہ 1/2^u امکان نال بچدا؛ سارے جیوندے چھلیاں اُتے جمع کیتے جان تے، ایہہ نمبر متوقع بچن والیاں دی گنتی دیندے نیں۔ کسے زنجیر دا فیصلہ کرنا اوس چون نوں چاہن والے ہر چھلے دا حصہ دُگنا کر دیندا اے تے باقیاں دا صفر۔ الگورتھم اوہ راہ چُندا اے جو جوڑ نوں ڈِگن نہیں دیندا، تاں جے آخر وچ گھٹ توں گھٹ اونے چھلیاں دی مدد ہووے جِنیاں دی اوسطاً قسمت مدد کردی۔

اک حد، سٹاپ واچ نہیں

مقالہ کوئی عملی نفاذ (implementation) یا چلن دا ویلا نہیں دسدا، تے “n دے تناسب” وچ لُکے مستقل (constants) نہیں دتے گئے۔ ایہہ وڈے نیں: 8,202 نمونیاں وچوں ہر اک لئی، الگورتھم ایہہ سانبھدا اے کہ اوہدے چھلے دی ہر رنگائی نوں کِنیاں سدھار والیاں تبدیلیاں دی لوڑ اے — “جانکاری دی اک بہت وڈی مستقل مقدار”۔ اک ضمیمے وچ، اوہ 2013 دی اک اجیہی اک دوجے اندر علاقیاں دی بنتر وچ “اک نکی غلطی” وی ٹھیک کردے نیں جیہدے اُتے اوہ اسار کردے نیں۔ 1852 دا اک قیاس ہُن اک اجیہے رنگن دے طریقے نال آؤندا اے جیہدی لاگت اوس نقشے توں تیز نہیں ودھدی جیہنوں اوہ رنگدا اے۔