FIŠ - Fakulteta za informacijske študije

Barvanja, dekompozicije in pokritja grafov (J1-1692)

Obdobje poteka: 01. 07. 2019―30. 06. 2022 

Sofinancer:  Javna agencija za raziskovalno dejavnost Republike Slovenije (ARRS)

Sodeluje: Laboratorij za kompleksne sisteme in podatkovne znanosti

Naziv projekta: Barvanja, dekompozicije in pokritja grafov (Graph Colorings, Decompositions and Coverings)

Vrsta projekta: Razvojno-raziskovalni projekt

Vloga FIŠ: Partner

Partnerji: Vodilni prijavitelj je UL Fakulteta za matematiko in fiziko

----------

Po skromnih začetkih pred skoraj 300 leti je v zadnjega pol stoletja področje teorije grafov doživelo velikanski skok naprej in postalo eno izmed glavnih področij sodobnih raziskav v matematiki. Na krilih uporabnosti rezultatov v tehnologiji, se področje raziskovanja nenehno širi, dosežki zadnjih let pa so nam dali zakladnico rezultatov, metod, idej in problemov. V zadnjih desetletjih je imela slovenska šola teorije grafov pomembno vlogo pri razvoju te matematične discipline na svetovni ravni do te mere, da je njena mednarodna prepoznavnost dandanes primerljiva s šolami tehnološko najbolj razvitih držav po svetu.

Naš projekt je usmerjen na določene vidike kromatične teorije grafov. Eden izmed osnovnih problemov v matematiki je razdelitev množice objektov na razrede tako, da upoštevamo določena pravila. Pri kromatični teoriji grafov želimo diskretni objekt razdeliti na enostavnejše podobjekte. Če so določena pravila enostavna, to še ne pomeni, da bo enostavno tudi reševanje z njimi povezanih problemov, ravno obratno! V okviru raziskav se bomo osredotočili na dve moderni in obetajoči raziskovalni temi s področij barvanj povezav in pokritij grafov.

Prva (oziroma druga) tema preučuje možnosti za zagotavljanje parnostne regularnosti (oziroma lokalne iregularnosti) na grafih preko barvanj njihovih povezav. Zanimanje za prvo od omenjenih tem izhaja iz starejšega rezultata (iz leta 1978), ki podaja povezavo med nikjer-ničelnimi pretoki in pokritji po povezavah sodih podgrafov. Ta del projekta predstavlja nadaljevanje že začetega dela na lihih barvanjih povezav (oziroma lihih pokritij) grafov, kot tudi njegove posplošitve, imenovane vozliščno-parnostno barvanje (pokritje) povezav.

Začetek raziskovanja druge teme sega v leto 1986 in je povezano s konceptom, znanim pod imenom iregularna moč grafa. To področje je bilo v zadnjih 15 letih predmet velikega zanimanja, kar se kaže tudi v treh znanih domnevah: Domnevi 1-2-3 (2004), Domnevi o detekciji (2005) in Domnevi o lokalni iregularnosti (2015). 
Domneve se (po vrstnem redu) nanašajo na najmanjše število barv, ki jih potrebujemo za razlikovanje glede na vsoto barv v soseščini vozlišč oziroma za razlikovanje glede na multimnožico barv v soseščini vozlišč oziroma lokalno iregularno barvanje povezav danega obarljivega grafa. Zaenkrat kaže, da trenutno znanje ne zadošča za rešitev teh domnev v celoti, zato nameravamo proučevati določene posebne vidike teh domnev na zoženih družinah grafov. 

Čeprav ne izgleda, da med omenjenimi barvanji obstaja očitna povezava, je bil rezultat o vozliščno-parnostnem barvanju povezav uporabljen za dokaz trenutno najboljše zgornje meje o (lokalno) iregularnem kromatičnem indeksu grafa. Načrtujemo bolj sistematično raziskavo nakazanih povezav, da bi jih našli še več. Navadno raziskovanje različic problemov barvanja pripomore k napredku reševanja originalnega problema. V ta namen se bomo v tretjem delu projekta osredotočili na študijo seznamskih različic in različic pokritij, povezanih z zgoraj omenjenimi barvanji.

Vodja projekta: prof. dr. Riste Škrekovski