LAUNI HUƊU GA KOWACE TASWIRA, A CIKIN LOKACI MAI LAYI

Duk wata taswira da aka zana a kan takarda mai faɗi za a iya yi mata launi da launuka huɗu ta yadda ƙasashe maƙwabta ba za su taɓa raba launi ɗaya ba. Francis Guthrie ya yi wannan hasashe a 1852; Appel da Haken sun tabbatar da shi a 1976. Amma ka’idar tana cewa ne kawai launuka huɗu suna akwai. Ta yaya za a samo su ga wata taswira? “Babu amsa mai sauƙi,” in ji Yuta Inoue, na Jami’ar Tokyo, da abokan aiki biyar daga Japan, Kanada, Slovenia da Denmark. Ya kasance mai sarƙaƙiya har ya kai ga gabatar da misalan ƙaryatawa (counterexamples) da yawa.

Ɗigo, layuka da alwatika

Kowace ƙasa tana zama ɗigo, ko vertex, kuma kowace iyaka da aka raba tana zama layi, ko edge: taswirar tana zama graph mai faɗi (planar graph), wanda aka zana ba tare da layuka sun ratsa juna ba. Yi masa launi yana nufin ba kowane vertex ɗaya daga cikin launuka huɗu, daban a ƙarshen biyu na kowane edge. Bari n ya zama adadin vertex. Ya isa a kula da triangulations, inda kowace fuska alwatika ce: ƙarin edge suna ƙara wahalar yin launi ne kawai.

Musanyar Kempe

Matakin asali ya samo asali daga wata takarda ta 1879 ta A. B. Kempe. Haɗa launukan huɗu biyu-biyu, misali ja da shuɗi, kore da rawaya. Sarƙar Kempe (Kempe chain) rukuni ne mai haɗe na vertex da ke sanye da launuka biyu na wani nau’i ɗaya. Musanya waɗannan launuka biyu a duk tsawon sarƙa yana barin launuka su ci gaba da zama daidai.

Ɗauki vertex v mai maƙwabta huɗu, v0 zuwa v3 bi da bi a kewaye da shi, kuma ka fara yi wa sauran launi. Idan maƙwabtan suna amfani da launi uku ko ƙasa da haka, v yana ɗaukar wanda ya rage. Idan suna amfani da dukan huɗun, bi sarƙar da ta fara daga v0 a cikin launukan v0 da v2. Idan ba ta kai v2 ba, musanya ta: v0 yana ɗaukar launin v2, ya bar wanda v zai ɗauka. Idan ta kai v2, maimakon haka ka musanya sarƙar v1 a cikin launukan v1 da v3, ta yadda v1 zai ɗauki launin v3.

Sassan da koyaushe za a iya gyarawa

Hujjojin ka’idar sun dogara ne kan tsare-tsaren da za a iya ragewa (reducible configurations): ƙananan siffofi da za a iya yanke su, sannan a mayar da su da zarar an yi wa sauran launi. Idan launukan zobensu (ring) — vertex da ke kewaye da su kai tsaye — ba su dace ba, ƙayyadadden adadin sauye-sauyen Kempe masu inganta abu da aka yi a waje koyaushe yana gyara su: 25 a mafi yawa ga siffofin da aka yi amfani da su a nan, waɗanda zobensu ke da vertex 18 a mafi yawa.

Tsarin da za a iya ragewa (hagu; kowace lamba ita ce adadin maƙwabtan da wannan vertex dole ya kasance da su a cikakkiyar taswira) da wannan siffar da aka cika da zobenta R (dama). — Hoto na 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour da Thomas sun nuna a 1997 yadda ake yin launi ta wannan hanya, siffa ɗaya a lokaci guda. Kowane zagaye yana rage graph ɗin da ’yan vertex kaɗan kuma yana biyan zagaye kan dukansa, don haka lokacin murabba’i ne (quadratic): ninki huɗu na tsawo ga taswira da ta ninka girma biyu.

A wata takarda ta baya (FOCS’26), marubutan shida ɗin sun tabbatar da cewa kowace triangulation tana ɗauke da adadin tsare-tsaren da za a iya ragewa da ba sa taɓa juna wanda ya yi daidai da n, da aka ɗauko daga jerin 8,202 — ko adadi iri ɗaya na gajerun da’irori masu vertex a ɓangarorin biyu, waɗanda su ma suke taimakawa. Suna cire dukan siffofin lokaci guda, su yi wa sauran launi, sannan su gyara dukan zobba tare. Sauyin Kempe na bazata yana taimaka wa wani zobe idan ya zaɓi daidaitaccen haɗin launuka (dama ɗaya cikin uku) da daidaitaccen jefa tsabar kuɗi a kan kowace sarƙa da ke taɓa zoben (dama ɗaya cikin biyu kowanne). Da irin waɗannan sarƙoƙi har 18, wannan aƙalla dama ɗaya ce cikin 3 × 2¹⁸, wato 786,432: ƙarami, amma tsayayye. Don haka adadin zagaye yana girma ne kamar log n kawai, kusan adadin lokutan da za a iya raba n biyu. Amma sauyi ɗaya zai iya shafar wani tsayayyen ɓangare na graph ɗin: kowanne yana biyan cikakken zagaye, n log n gaba ɗaya.

Tebur maimakon zagaye

Sabuwar takardar tana riƙe da sauye-sauye log n amma tana sa kowanne ya fi arha. Bayan shiri da ke ɗaukar lokacin da ya yi daidai da n, ana samo kowane sauyi kuma a aiwatar da shi cikin kusan matakai n / log n a matsakaici. Sauye-sauyen log n tare sai su ɗauki lokacin da ya yi daidai da n — lokaci mai layi (linear time) — iyakar da marubutan ke kira mafi kyau da zai yiwu (optimal).

Dabarar ita ce “Hanyar ’Yan Rasha Huɗu” (Method of Four Russians). Ƙaramar matsala da ta dace cikin lambar bit ½ log n — rabin lambobin binary da ake buƙata don rubuta n — tana da nau’ikan da za su yiwu √n a mafi yawa, don haka za a iya lissafa amsoshinsu duka tun da wuri a ajiye su cikin tebur. Kwamfutar da aka ɗauka, mai kalmomin ƙwaƙwalwa na kusan bit log n, tana karanta duk wata amsa da aka ajiye a mataki ɗaya.

Ana yanka graph ɗin, sau da sau, zuwa yankuna da ke cikin juna masu gajerun iyakoki. Mafi ƙanƙanta suna ɗauke da kusan vertex log n kuma suna dacewa, tare da launuka, cikin lamba ɗaya. Ga kowane yanki, ƙaramin graph na taƙaitawa yana rubuta waɗanne vertex na iyaka ke raba sarƙar Kempe. Sauyi sai ya sauka a matsayin jerin bit na “musanya” ko “bari”, kuma a kowane ƙaramin yanki, duba ɗaya yana sabunta kowane launi.

Ɓangaren graph da aka yi wa launi da launuka huɗu. Yankin mai launin toka shi ne yanki R; edge baƙaƙe masu kauri na sarƙoƙin Kempe ne na nau’ikan ja-shuɗi da kore-rawaya. — Hoto na 2, Inoue et al. (2026), arXiv:2610.39753.

Taƙaitawar wannan yanki: kowane ɗunƙulen shuɗi yana wakiltar ɓangaren sarƙar Kempe, kuma layukansa suna nuna waɗanne vertex na iyaka yake haɗawa. — Hoto na 3, Inoue et al. (2026), arXiv:2610.39753.

Zaɓi ba tare da ɗan caca ba

Da zaɓe na bazata, wannan ya riga ya yi wa taswira launi cikin lokaci mai layi a matsakaici. Cire ɗan cacar ba tare da rasa sauri ba shi ne “ɓangare mafi wahala nesa ba kusa ba”. Ka kira zobe mai rai muddin kowane hukunci zuwa yanzu ya tafi yadda yake so. Idan aka bar sarƙoƙi u da ba a yanke hukunci a kansu ba da ke taɓa shi ga jefa tsabar kuɗi, zai tsira da yiwuwar 1/2^u; idan aka tara a kan dukan zobba masu rai, waɗannan lambobi suna ba da adadin waɗanda ake tsammani za su tsira. Yanke hukunci kan sarƙa yana ninka sashen kowane zobe da ya so wannan zaɓi biyu kuma yana mayar da na sauran sifili. Algorithm ɗin yana ɗaukar zaɓin da ke hana jimillar faɗuwa, ta yadda a ƙarshe za a taimaka wa aƙalla adadin zobban da sa’a za ta taimaka wa a matsakaici.

Iyaka, ba agogon gudu ba

Takardar ba ta ba da rahoton aiwatarwa (implementation) ko lokacin gudu ba, kuma ba a ba da tsayayyun lambobin (constants) da ke ɓoye a cikin “ya yi daidai da n” ba. Suna da girma: ga kowace daga cikin siffofi 8,202, algorithm ɗin yana ajiye adadin sauye-sauye masu inganta abu da kowane launi na zobenta ke buƙata — “wani gagarumin adadin bayani tsayayye”. A wani ƙarin bayani (appendix), sun kuma gyara “ƙaramin kuskure” a cikin ginin yankuna masu cikin juna na 2013 da suka gina a kai. Hasashe daga 1852 yanzu yana zuwa da hanyar yin launi wadda tsadarta ba ta girma da sauri fiye da taswirar da take yi wa launi.