Obdobje poteka: 01. 01. 2020—31. 12. 2021

Sofinancer: ARRS

Sodeluje: Laboratorij za kompleksne sisteme in podatkovne znanosti

Naziv projekta: Lastnosti in odvisnosti kromatičnih invariant grafov (Properties and dependencies of chromatic graph invariants)

Vrsta projekta: Razvojno-raziskovalni projekt

Vloga FIŠ: Vodilni prijavitelj na slovenski strani

Partner: University of Montpellier

———-

Osnovni problem kromatične teorije grafov je določiti najmanjše število barv, s katerimi lahko pobarvamo vozlišča grafa tako, da so sosednja vozlišča obarvana različno. Problem je v splošnem, tako kot velika večina njegovih izpeljank, NP-težek. Že pri študiju osnovnega problema je obravnava grafov celovita. Poznati je potrebno njihove strukturne lastnosti, npr. v razredih grafov na ploskvah se s pridom uporabljajo rezultati topološke teorije grafov, pri grafih z visoko stopnjo simetrije pa rezultati s področja algebraične teorije grafov. Konec prejšnjega stoletja se je za izboljšanje obstoječih mej vse bolj začelo uporabljati verjetnostne pristope, ki so dokazovali obstoj barvanj z omejenim število barv s pozitivno verjetnostjo.

Z leti so se poleg osnovnega začeli pojavljati še drugi tipi barvanj, motivirani z uporabo v praksi ali pa preprosto z odnosi med grafovskimi objekti. Eno izmed bolj plodnih področij je z Vizingovim dokazom, da je minimalno število potrebnih barv enako maksimalni stopnji grafa oziroma eni barvi več, postalo barvanje povezav. Barvanje povezav grafa je sicer ekvivalentno barvanju vozlišč povezavnega grafa, pa vendar ima študij tega problema posebno privlačnost, zaradi lastnosti, ki so specifične za povezavne grafe. Ravno zato so različne kromatične invariante, ki imajo za domeno vozlišča, dobile svojo različico tudi v smislu povezav.

Krepko barvanje povezav je barvanje povezav, pri katerem povezavam priredimo barve tako, da je par povezav na medsebojni razdalji kvečjemu dva, obarvan različno. Trideset let stara domneva, ki sta jo postavila Erdős in Nešetřil, je, da za takšno barvanje zadošča 1.25 ∆(G)^2 barv, trenutno najboljša zgornja meja pa je 1.83 ∆(G)^2 iz leta 2015, dokazana s pomočjo verjetnostne metode in še ta velja le za grafe z dovolj visoko maksimalno stopnjo.

Podobno daleč oziroma še precej dlje smo pri dokazovanju domnevane meje ∆(G) + 2 za aciklično barvanje povezav, pri katerem povezave barvamo tako, da v grafu ne nastane dvobarvni cikel in pogojem, da so dotikajoče se povezave obarvane različno. Tudi pri tej invarianti se dokaz trenutno najboljše meje, 4 (∆(G)-1), opira na uporabo verjetnosti s tako imenovano metodo stiskanja entropije.

V obeh opisanih primerih, se številu barv z verjetnostno metodo približujemo z izboljševanjem konstante pri vodilnem členu, medtem ko je red velikosti le-tega že pravi. Obstajajo pa še težji primeri: v letu 2012, so se Dvořák, Mohar in Šamál ukvarjali z zvezdnim barvanjem povezav, ki je pravilno barvanje povezav, z dodatno predpostavko, da v grafu ne nastanejo dvobarvne poti oziroma cikli na štirih povezavah. Dokazali so, da je za takšno barvanje polnega grafa na n vozliščih potrebnih največ n^(1+ε) barv in vprašali ali morda ne zadošča število barv, ki je linearno v številu vozlišč. Problem je še vedno široko odprt.

Zgoraj našteti problemi so si na videz podobni, pa vendar vsaka dodatna predpostavka zahteva poglobljeno razumevanje novih lastnosti grafov. Vsem razlikam navkljub, se pri reševanju teh problemov za splošne grafe običajno izkaže, da je pristop z uporabo orodij teorije verjetnosti najbolj učinkovit. Po drugi strani, omejitev na ožje razrede grafov pokaže, da verjetnostna orodja ne premorejo primerne natančnosti, ko se želimo približati pravim mejam. V teh primerih je v veliki meri potrebno odlično razumevanje strukture grafov, kar se je lepo pokazalo pri dokazovanju Izreka štirih barv in večini rezultatov v razredu kubičnih grafov.

Problemi, ki jih rešujemo raziskovalci na tem bogatem področju so temeljne narave. Razširiti želimo razumevanje lastnosti kromatičnih invariant, razviti metode, s katerimi bomo te lastnosti lažje odkrili in posledično izboljšati obstoječe rezultate.

Vodja bilateralnega projekta v Sloveniji: izr. prof. dr. Borut Lužar

Vodja bilateralnega projekta v partnerski državi (ZDA): dr. Stéphane Bessy (University of Montpellier)