Obdobje poteka: 01. 10. 2019—30. 09. 2021
Sofinancer: ARRS
Sodeluje: Laboratorij za kompleksne sisteme in podatkovne znanosti
Od pravilnih do krepkih barvanj povezav (Znanstvenoraziskovalno sodelovanje z Republiko Slovenijo in ZDA 2019-2021)
Obdobje poteka: 01. 10. 2019—30. 09. 2021
Sofinancer: ARRS
Sodeluje: Laboratorij za kompleksne sisteme in podatkovne znanosti
Naziv projekta: Od pravilnih do krepkih barvanj povezav (From proper to strong edge-colorings)
Vrsta projekta: Razvojno-raziskovalni projekt
Vloga FIŠ: Vodilni prijavitelj na slovenski strani
Partner: Iowa State University, Department of Mathematics
———-
Barvanje povezav je različica barvanj, pri kateri namesto vozlišč barvamo povezave. Barvanje povezav je pravilno, če sosednje povezave prejmejo različne barve. Vizing je dokazal osrednji rezultat tega področja, ki pravi, da za barvanje povezav potrebujemo največ toliko barv, kot je maksimalna stopnja grafa ali eno bravo več. Čeprav so barvanja povezav pravzaprav ekvivalentna barvanju vozlišč povezavnih grafov, je sam problem zanimiv zaradi specifičnih lastnosti tovrstnih grafov. To je eden izmed poglavitnih razlogov, da so različne kromatične invariante iz domene vozlišč dobile svoje analoge tudi v povezavni različici.
Pomembna varianta barvanj povezav so krepka barvanja povezav, kjer poleg pravilnega barvanja zahtevamo še, da so povezave na razdalji 2 pobarvane različno (razdaljo med povezavami definiramo kot razdaljo med pripadajočimi vozlišči v povezavnem grafu). Pred kratkim je bila objavljena sistematična študija barvanj povezav, ki ležijo med pravilnimi in krepkimi barvanji, avtorja pa sta Gastineau in Togni. Pravzaprav sta jih definirala v širšem okvirju S-pakirnih barvanj povezav. Za dano nepadajoče zaporedje naravnih števil S = (s_1,…, s_k) je S-pakirno barvanje povezav dekompozicija povezav v disjunktne množice X_1,…, X_k, kjer so povezave v množici X_i paroma na razdalji vsaj s_i. Množica X_i se imenuje s_i-pakiranje; npr. 1-pakiranje je navadno prirejanje, 2-pakiranje pa inducirano prirejanje. Pojem S-pakirnih barvanj povezav je motiviran z vozliščnim analogom, ki sta ga predstavila Goddard in Xu kot naravno posplošitev problema pakiranja vozlišč.
Zaenkrat študij zajema zgolj grafe z maksimalno stopnjo 3 (t.j. subkubične grafe). Vizingov rezultat v prevodu v S-pakirna barvanja torej pravi, da ima vsak subkubični graf (1,1,1,1)-pakirno barvanje povezav, medtem ko imajo grafi iz razreda I (1,1,1)-pakirno barvanje. Rezultat, ki so ga dokazali Payan, Fouquet in Vanherpe, pove še več, namreč, da za vsak subkubični graf obstaja (1, 1, 1, 2)-pakirno barvanje povezav. Pri tem 2 ne moremo nadomestiti s 3, saj npr. v Petersenovem grafu in Tietzejevem grafu to ni možno.
Zmanjševanje števila 1 v zaporedjih poveča število potrebnih barv, t.j. dolžino zaporedja. Če v zaporedju ni nobene 1, potem imamo opravka s krepkim barvanjem. Andersen in neodvisno Horák, Qing in Trotter so dokazali, da 10 barv vedno zadošča za barvanje subkubičnih grafov, da imajo torej (2^10)-pakirno barvanje povezav. Meja 10 barv je natančna. Pravilno in krepko barvanje subkubičnih grafov sta bila obravnana že v prejšnjem stoletju, Gastineau in Togni pa sta začela polniti praznino s študijem (1^k, 2^l)-pakirnih barvanj povezav za k = 1, 2. Dokazala sta, da ima vsak kubični graf z 2-faktorjem (1, 1, 2^5)-pakirno barvanje povezav in da se število 2-pakiranj pri grafih iz razreda I zmanjša za 1. Natančne meje so zelo verjetno nižje. Kakšne so natančne meje za dvodelne grafe, ravninske grafe, grafe z velikim notranjim obsegom ipd. je odprto vprašanje. Te probleme želimo obravnavati v sklopu predlaganega projekta. Obe skupini sta že študirali krepka barvanja povezav, pri čemer sta uporabljali različne metode, zato verjamemo, da bo združitev znanja in izkušenj zagotovilo uspešnost projekta.
Vodja bilateralnega projekta v Sloveniji: izr. prof. dr. Borut Lužar
Vodja bilateralnega projekta v partnerski državi (ZDA): dr. Bernard Lidický (Iowa State University)
