Raziskovalni projekt (so)financira Javna agencija za raziskovalno dejavnost RS.
Članica UL: Fakulteta za matematiko in fiziko
Šifra projekta: J1-3002
Naziv projekta: Prirejanja in barvanja povezav v kubičnih grafih
Obdobje: 1. 10. 2021 - 30. 9. 2024
Letni obseg: 1,4 FTE, cenovna kategorija: C
Vodja: Riste Škrekovski
Veda: Naravoslovje
Sodelujoče RO, sestava projektne skupine in bibliografske reference
Vsebinski 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.
Rezultati in dosežki projekta:
Opis realizacije programa dela je razdeljen na tri stebre, katerim se v okviru projekta posvečamo. V vsakem od stebrov navajamo cilje, ki so pravzaprav odprti problemi, katerim smo se posvečali tekom izvajanja projekta.
Steber 1 - Fanova barvanja
V predlogu projekta smo predvideli reševanje problemov iz tega sklopa v začetku izvajanja, vendar smo se ob začetku izvajanja odločili, da s problemi tega sklopa počakamo do druge polovice izvajanja, saj smo vmes s sodelavci iz tujine (iz laboratorijev v Bordeauxu, Bratislavi in Košicah) začeli oz. nadaljevali aktivnosti na problemih Stebrov 2 in 3, ki jih opisujemo spodaj.
Steber 2 - Normalna barvanja povezav
V sklopu normalnih barvanj delamo na identifikaciji različnih lastnosti teh barvanj v kubičnih grafih. Predvsem na določanju barvanj, ki so sorodna normalnim, npr. pravilna barvanja povezav z majhnim dovoljenim številom srednjih povezav (to so povezave, ki niso niti revne niti bogate). V tem kontekstu smo objavili članek [1], ki sicer prihaja iz tematike pakirnih barvanj, vendar ga lahko interpretiramo v jeziku normalnih barvanj, če omejimo število krepkih barv. Barve, s katerimi barvamo povezave grafa, namreč razdelimo na pravilne in krepke. Povezave obarvane z isto pravilno barvo morajo biti neodvisne, medtem ko morajo biti povezave obarvane z isto krepko barvo na medsebojni razdalji vsaj 3.
Ukvarjali smo se tudi z normalnim barvanjem povezav snarkov G', ki jih dobimo s superpozicijo povezav in vozlišč cikla v nekem snarku G. Za sod cikel C pokažemo, da lahko normalno barvanje G razširimo v normalno barvanje G', ne da bi spremenili barve povezav, ki niso na C v G. Tega v splošnem ne moremo storiti, če je C lih cikel. Članek je v zaključni fazi pred oddajo.
V kontekstu Problemov 35 in 36 ter z navezavo na [1] smo začeli še s študijem barvanj povezav, kjer za vsako povezavo zahtevamo, da je sosednja z vsaj k bogatimi povezavami. Imamo že nekaj rezultatov in priprava inicialnega članka se bliža zaključku. Verjamemo, da bo ta smer odprla precej vprašanj in pokazala dodatne povezave tako z normalnimi barvanji kot z barvanji, ki jih bomo obravnavali v prvem stebru v nadaljevanju projekta.
Omenimo še, da je bila v letu 2022 že dokazana Domneva 14 (pravzaprav njena močnejša verzija) iz predloga našega projekta. Dokazali so jo Kardoš, Máčajová in Zerafa [2], s katerimi sicer sodelujemo pri nekaterih drugih projektih. Natančneje, dokazali so, da za dani (1^+)-faktor F in poljubno povezavo e grafa G vedno obstaja popolno prirejanje M za G, ki vsebuje e, tako da je G \ (F U M) dvodelni graf.
[1] H. Hocquard, D. Lajou, B. Lužar: Between proper and strong edge-colorings of subcubic graphs, J. Graph Theory 101 (2022), 686-716. [COBISS-ID: 117622019]
[2] F. Kardoš, E. Máčajová, P. Zerafa: Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching. J. Comb. Theory Ser. B 160 (2023), 1-14.
Steber 3 - Krepka barvanja povezav
V planu dela smo imeli v načrtu obravnavo Problemov 40, 41 in 44.
Preden začnemo z opisom trenutnega stanja na njih, omenimo še, da smo objavili članek [3], v katerem smo klasificirali regularne grafe s krepkim kromatičnim indeksom enakim 2D-1, kjer je D maksimalna stopnja grafa. Če imamo v grafu vsaj dve sosednji vozlišči maksimalne stopnje, potrebujemo vsaj 2D-1 barv za krepko barvanje. Dokazali smo, da to število barv zadošča natanko za grafe, ki pokrijejo Kneserjeve grafe K(2D-1, D-1). V kubičnih grafih so to natanko grafi, ki pokrijejo Petersenov graf. Gre za zelo omejen razred in vanj na primer ne spadajo skoraj vsi grafi s poljubno velikim notranjim obsegom. To pomeni, da za kubične grafe z velikim notranjim obsegom potrebujemo vsaj 6 barv. Trenutno intenzivno delamo na klasifikaciji kubičnih grafov, ki imajo krepki kromatični indeks enak 6, vendar povezave med notranjim obsegom in majhnim številom potrebnih barv še nismo uspeli dokazati, če ta sploh obstaja. Nekatere lastnosti celo kažejo na to, da takšne povezave ni. V kontekstu barvanja s 6 barvami delamo še na razredu prirezanih kubičnih grafov (truncated cubic graphs), kjer se vsako vozlišče nadomesti s trikotnikom. Ukvarjamo se z zaključnimi detajli dokaza, da takšni grafi potrebujejo 6 barv. Pričakujemo, da bomo članek objavili v kratkem. Hkrati z določanjem lastnosti se že ukvarjamo tudi z iskanjem potrebnih in zadostnih pogojev za kubične grafe s krepkimi kromatičnimi indeksi enakimi 7, 8 in 9, kar spada v kontekst problemov 42, 43 in 44.
Delo na krepkih barvanjih povezav smo dopolnili še z rezultatom o polkrepkih barvanjih, ki zahtevajo 'krepko' oddaljenost povezav enake barve samo oziroma vsaj od enega krajišča dane povezave. To pomeni, da povezava, ki je pobarvana s krepko barvo, lahko ima povezavo enake barve, ki je od enega krajišča oddaljena manj kot 3, medtem ko mora biti razdalja do drugega krajišča vsaj 3. Dokazali smo, da za takšno barvanje kubičnih grafov zadošča 8 barv, medtem ko domnevamo, da jih zadošča celo zgolj 7, ko izločimo dva posebna grafa. Članek je še v recenziji, objavljen pa je kot preprint [4].
[3] B. Lužar, E. Máčajová, M. Škoviera, R. Soták: Strong edge colorings of graphs and the covers of Kneser graphs, J. Graph Theory 100(4) (2022), 686-697. [COBISS-ID: 98955267]
[4] B. Lužar, M. Mockovčiaková, R. Soták: Revisiting Semistrong Edge-Coloring of Graphs (2022), arXiv:2208.13297.
