Koliko različitih boja je potrebno da bi sve međusobno spojene tačke grafikona bile različite boje ?

"Nažalost, gotovo da je nemoguće naći opšte rješenje za sve moguće grafove", rekao je Julie Rehmeyer za Science News. "Ipak, nakon čitave jedne dekade napornog rada tim matematičara je uspio izdvojiti jednu specifičnu vrstu grafova za koje je moguće riješti navedeni problem, te grafove nazivamo "perfektnim" grafovima."

"Pretpostavimo da imamo grupu čvorova i da je svaki od njih spojen sa svim ostalim čvorovima", govori Rehmeyer. "Svaki čvor iz te grupe treba biti različite boje. To znači da graf treba imati, u najmanju ruku, toliko boja koliko ima članova najveća grupa međusobno spojenih čvorova i još malo više. Ako je taj broj (nazvan "grupni broj") boja dovoljan graf se zove "perfektan graf"."


Ipak odrediti koji su grafovi perfektni nije nimalo jednostavan zadatak. Claude Berge je 1960. godine postavio hipotezu koju nije uspio dokazati.

Na odgovor se čekalo sve do 2006. godine kad su Paul Seymour (Prinenton univerzitet), Robin Thomas (Georgia tehnološki institut), Neil Robertson (Ohio državni univerzitet) i Maria Chudnovsky (Columbia univerzitet) objavili dokaz.

"To je brilijantan dokaz", rekao je Gerard Cornuejols sa Carnegie Mellon i d'Aix-Marseille univerziteta koji je svojim idejama pomogao da tim dokaže hipotezu. Takođe je i ponudio 5000 američkih dolara svog novca onome ko uspije u dokazivanju, ovaj novac je posljedično pripao navedenom timu matematičara.

Još dosta grafova je ostalo neobojeno tako da matematičari nastavljaju sa razvojem algoritama za efikasno detektovanje perfektnih grafova i metoda za nalaženjem minimalnog broja boja za koji je Bergeova "teorema grafova" pokazala da mora postojati.

Izvor: Science News, 6. mart 2009.