Nalaganje ...
Projekti / Programi vir: ARIS

Barvanja, dekompozicije in pokritja grafov

Raziskovalna dejavnost

Koda Veda Področje Podpodročje
1.01.05  Naravoslovje  Matematika  Teorija grafov 

Koda Veda Področje
P110  Naravoslovno-matematične vede  Matematična logika, teorija množic, kombinatorika 

Koda Veda Področje
1.01  Naravoslovne vede  Matematika 
Ključne besede
barvanje grafa, pretok, dekompozicija, pokritje, faktor, T-spoj
Vrednotenje (pravilnik)
vir: COBISS
Raziskovalci (22)
št. Evidenčna št. Ime in priimek Razisk. področje Vloga Obdobje Štev. publikacijŠtev. publikacij
1.  31774  dr. Klen Čopič Pucihar  Računalništvo in informatika  Raziskovalec  2019 - 2022  153 
2.  50728  dr. Darko Dimitrov  Matematika  Raziskovalec  2019 - 2022  79 
3.  55262  dr. Tomislav Došlić  Matematika  Raziskovalec  2022  83 
4.  29665  dr. Rija Erveš  Matematika  Raziskovalec  2019 - 2022  52 
5.  35875  Marjeta Grahek    Tehnični sodelavec  2020 - 2022 
6.  38085  dr. Petr Gregor  Matematika  Raziskovalec  2019 - 2022  40 
7.  33510  dr. Jelena Klisara  Matematika  Raziskovalec  2019 - 2022  16 
8.  24897  dr. Matjaž Kljun  Računalništvo in informatika  Raziskovalec  2019 - 2022  178 
9.  36238  dr. Martin Knor  Matematika  Raziskovalec  2019 - 2022  119 
10.  34562  dr. Matjaž Krnc  Matematika  Raziskovalec  2019 - 2022  95 
11.  27800  dr. Zoran Levnajić  Fizika  Raziskovalec  2019 - 2022  135 
12.  31670  dr. Borut Lužar  Računalniško intenzivne metode in aplikacije  Raziskovalec  2019 - 2022  184 
13.  55615  dr. Mirko Petrushevski  Matematika  Raziskovalec  2021 - 2022  35 
14.  18838  dr. Primož Potočnik  Matematika  Raziskovalec  2019 - 2022  239 
15.  37541  dr. Alejandra Ramos Rivera  Matematika  Raziskovalec  2021 - 2022  18 
16.  32250  dr. Polona Repolusk  Interdisciplinarne raziskave  Raziskovalec  2020  47 
17.  55478  dr. Jelena Sedlar  Matematika  Raziskovalec  2022  40 
18.  36239  dr. Roman Sotak  Matematika  Raziskovalec  2019 - 2022  62 
19.  15518  dr. Riste Škrekovski  Matematika  Vodja  2019 - 2022  518 
20.  53598  dr. Kenny Štorgel  Matematika  Mladi raziskovalec  2020 - 2022  22 
21.  23904  dr. Aleksandra Tepeh  Matematika  Raziskovalec  2019 - 2022  132 
22.  30920  dr. Janoš Vidali  Matematika  Raziskovalec  2019 - 2022  26 
Organizacije (2)
št. Evidenčna št. Razisk. organizacija Kraj Matična številka Štev. publikacijŠtev. publikacij
1.  1554  Univerza v Ljubljani, Fakulteta za matematiko in fiziko  Ljubljana  1627007  34.545 
2.  2784  Fakulteta za informacijske študije v Novem mestu  Novo mesto  3375650  6.191 
Povzetek
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š predlog projekta 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 predlaganih 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.
Pomen za razvoj znanosti
Teorija grafov je moderna veja matematike, ki se je znatno razširila v zadnjem stoletju po zaslugi velikega napredka tehnologije in je široko uporabna na mnogih znanstvenih področjih kot so algoritmi v računalništvu, modeliranje molekul v kemiji, modeliranje komunikacijskih omrežij ter v študiju kompleksnih omrežij. Kromatična teorija grafov, katere razvoj se je začel v letu 1852 s slavnim Problemom štirih barv, je dandanes osrednje in najbolj obsežno področje teorije grafov. V okviru projekta bomo obravnavali probleme s področja barvanj grafov, ki so tesno povezani s teorijo pretokov, dekompozicij in sorodnih tematik, ki so trenutno vroče teme raziskovanja v moderni teoriji grafov. Z objavami v znanstvenih revijah najvišjega ranga, predstavitvami rezultatov na mednarodnih konferencah ter v sklopu seminarjev raziskovalnih skupin v tujini, bomo problematiko približali širšemu krogu raziskovalcev. Naši že objavljeni rezultati kažejo, da je področje zanimivo tudi za druge skupine, saj so članki, pa čeprav nedavni, že solidno citirani.
Pomen za razvoj Slovenije
Graph theory is a modern branch of mathematics, which has expanded significantly during the last century due to the enormous progress of technology, and it is widely applied in many diverse sciences such as algorithms in computer science, modeling molecules in chemistry, modeling communication networks, and studying complex networks. The chromatic graph theory, with its origins starting in 1852, is nowadays central and major part of graph theory. In the scope of the project, we will consider problems from chromatic graph theory which are closely related with the flow theory, graph decompositions and related thematics, which are currently hot topics in modern graph theory. By publishing our results in the scientific journal of the highest rank, presentations on international conferences and on seminars of foreign research groups, we will introduce the problematics to wider set of researchers. Our already published results show that these types of problems are interesting for various groups of researchers as our papers, yet recent, have already obtained a considerable number of citations.
Najpomembnejši znanstveni rezultati Vmesno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Zgodovina ogledov
Priljubljeno