Obdobje poteka: 01. 10. 2021―30. 9. 2024
Sofinancer: Javna agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Naziv projekta: Prirejanja in barvanja povezav v kubičnih grafih
Vrsta projekta: Razvojno-raziskovalni projekt
Opis projekta:
Projekt se osredotoča na nekatere vidike kromatične teorije grafov, znanstvenega področja, ki je od skromnih začetkov v zadnjem stoletju doživelo izjemno rast in doseglo precejšnjo globino. Dandanes velja za eno glavnih področij raziskav v matematiki.
Pravilno barvanje povezav (tj. barvanje povezav, tako da sosednje povezave prejmejo različne barve) kubičnih grafov predstavlja bistveni del kromatične teorije grafov, ki je tesno povezan z zgodovino njenega razvoja. Obsežne raziskave potekajo že več kot stoletje. Prvotna motivacija izhaja iz Taitovega poskusa rešitve slavnega Problema štirih barv, v naslednjih desetletjih pa je koncept vzpostavil tesne povezave z drugimi področji teorije grafov. Barvanje povezav deli kubične grafe na dva neenaka dela: razred Taitovo-obarvljivih (po povezavah 3-obarvljivih) grafov obsega skoraj vse kubične grafe, medtem ko je njegov komplement majhen razred grafov, ki potrebujejo 4 barve in za katere je znano, da so tesno povezani s številnimi izjemno težkimi problemi. Netrivialni člani slednje družine, imenovani snarki, lahko vključujejo protiprimere za Berge-Fulkersonovo domnevo in Domnevo o Petersenovem barvanju. Naše predvidene raziskave se osredotočajo na tri razširitve koncepta Taitovih barvanj, ki so močno povezane z omenjenima dvema zloglasnima domnevama; in sicer na Fanovo barvanje, normalno barvanje povezav in krepko barvanje povezav.
Številni problemi, ki vključujejo kubične grafe, se nanašajo na obstoj popolnih prirejanj, katerih presek je majhen ali prazen, kar je naravno, saj je obstoj dveh disjunktnih popolnih prirejanj ekvivalenten Taitovemu barvanju. Fan-Raspaudova domneva pravi, da vsak 2-povezan kubični graf vsebuje tri popolna prirejanja s praznim presekom. Ta poenostavitev Berge-Fulkersonove domneve se je nedavno pojavila v kontekstu Fanovih barvanj, posplošitve 3-barvanja povezav, ki točke Fanove ravnine dodeljujejo povezavam kubičnega grafa tako, da barve vsakih treh povezav s skupnim krajiščem tvorijo premico. Eden od ciljev naše raziskave je nadaljevanje študija problema najmanjšega števila premic, ki se pojavijo kot barvni vzorci okoli vozlišč. V tem smislu je Fanovo barvanje z eno premico Taitovo, medtem ko je Fanovo barvanje s 4 premicami ekvivalentno Fan-Raspaudovim popolnim prirejanjem.
Še eno posplošitev pravilnih barvanj povezav dobimo z nadomestitvijo globalnega pogoja glede števila barv z lokalnim. Ekvivalentna oblika Domneve o Petersenovem barvanju pravi, da vsak 2-povezan kubični graf dopušča pravilno barvanje povezav s 5 barvami, tako da so sosede vsake povezave pobarvane z 2 (revna povezava) ali 4 (bogata povezava) barvami; takšno barvanje imenujemo normalno. Ta oblika omogoča druge pristope k Petersenovem barvanju, tako da dovoli uporabo več ali manj kot 5 barv, in da je pogoj normalnosti izpolnjen na velikem delu povezav.
Pravilno 3-barvanje povezav kubičnega grafa je barvanje, pri katerem je vsaka povezava revna. Na drugi strani imamo krepko barvanje povezav, pri katerih je vsaka povezava bogata. Zadnje barvanje tvori tretjo smer našega projekta. Določanje zgornjih mej za krepko barvanje povezav splošnih grafov je še vedno aktualna in splošno raziskovana tema, reševanje vprašanj v zvezi s kubičnimi grafi pa nas bo približalo k rešitvi splošnega primera.
Glavni cilj projekta je (delno) razrešiti zgoraj omenjene probleme s preučevanjem kubičnih grafov pod določenimi predpostavkami. Izboljšali bomo obstoječe in razvili nove tehnike dokazovanja ter izboljšali razumevanje teh problemov. Rezultati projekta bodo pomembno vplivali na skupnost raziskovalcev barvanj grafov, saj so opisane domneve in njihove izpeljanke predmet številnih raziskav.
Vodja projekta: prof. dr. Riste Škrekovski
