Rangi nne zinatosha kwa ramani yoyote, ili majirani daima wawe na rangi tofauti. Hilo lilithibitishwa mwaka 1976. Lakini unazipataje rangi hizo kwa vitendo?
Chombo cha kawaida ni mnyororo wa Kempe. Chagua rangi mbili na uchukue eneo zima lililoungana la nchi zilizopakwa rangi hizo mbili tu. Zibadilishane kote katika eneo hilo: ramani inabaki imepakwa rangi ipasavyo.
Tatizo: ubadilishanaji mmoja unaweza kusambaa katika ramani nzima. Rekodi iliyotangulia ilihitaji ubadilishanaji zaidi kadiri ramani zilivyokua. Kila mmoja uligharimu kupitia ramani nzima.
Wanahisabati sita, kutoka Tokyo hadi Copenhagen, wameondoa gharama hiyo ya ziada. Algorithimu yao inapaka rangi nchi n kwa muda unaolingana na n. Vipande vidogo vya ramani vinatatuliwa mara moja, vinahifadhiwa katika majedwali, kisha vinatafutwa tu. Waandishi wanaiita kasi hii bora kabisa.
Chanzo: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










