Nalaganje ...
Projekti / Programi vir: ARIS

Prirejanja in barvanja povezav v kubičnih grafih

Raziskovalna dejavnost

Koda Veda Področje Podpodročje
1.01.00  Naravoslovje  Matematika   

Koda Veda Področje
1.01  Naravoslovne vede  Matematika 
Ključne besede
graf, prirejanje, barvanje, pretok, kubični graf, snark, Domneva o Petersenovem barvanju, Berge-Fulkersonova domneva
Vrednotenje (pravilnik)
vir: COBISS
Upoš. tč.
15.411,14
A''
190,79
A'
4.528,41
A1/2
7.704,07
CI10
7.273
CImax
166
h10
35
A1
47,59
A3
0,31
Podatki za zadnjih 5 let (citati za zadnjih 10 let) na dan 23. julij 2024; A3 za obdobje 2018-2022
Podatki za razpise ARIS ( 04.04.2019 - Programski razpis, arhiv )
Baza Povezani zapisi Citati Čisti citati Povprečje čistih citatov
WoS  782  8.131  6.631  8,48 
Scopus  854  9.579  7.926  9,28 
Raziskovalci (27)
št. Evidenčna št. Ime in priimek Razisk. področje Vloga Obdobje Štev. publikacijŠtev. publikacij
1.  17005  dr. Boštjan Brešar  Matematika  Raziskovalec  2021 - 2024  408 
2.  53750  Clement Jean Dallard  Matematika  Raziskovalec  2021 - 2022  32 
3.  50728  dr. Darko Dimitrov  Matematika  Raziskovalec  2022  79 
4.  55262  dr. Tomislav Došlić  Matematika  Raziskovalec  2023 - 2024  83 
5.  29665  dr. Rija Erveš  Matematika  Raziskovalec  2022  52 
6.  50186  dr. Jasmina Ferme  Matematika  Raziskovalec  2021 - 2024  51 
7.  37715  dr. Slobodan Filipovski  Matematika  Raziskovalec  2023 - 2024  40 
8.  35875  Marjeta Grahek    Tehnični sodelavec  2022 
9.  38085  dr. Petr Gregor  Matematika  Raziskovalec  2022 - 2024  40 
10.  36238  dr. Martin Knor  Matematika  Raziskovalec  2022 - 2024  119 
11.  56778  Maja Kocjan    Tehnični sodelavec  2022 - 2024 
12.  34562  dr. Matjaž Krnc  Matematika  Raziskovalec  2021 - 2024  95 
13.  51185  Mateja Lesar  Psihologija  Mladi raziskovalec  2022 - 2024 
14.  31670  dr. Borut Lužar  Računalniško intenzivne metode in aplikacije  Raziskovalec  2021 - 2024  184 
15.  37403  dr. Tilen Marc  Matematika  Raziskovalec  2022 - 2023  47 
16.  30211  dr. Martin Milanič  Matematika  Raziskovalec  2021 - 2024  314 
17.  55615  dr. Mirko Petrushevski  Matematika  Raziskovalec  2022 - 2024  35 
18.  53161  Jani Pogačar    Tehnični sodelavec  2022 - 2024 
19.  18838  dr. Primož Potočnik  Matematika  Raziskovalec  2021 - 2024  239 
20.  32250  dr. Polona Repolusk  Interdisciplinarne raziskave  Raziskovalec  2022  47 
21.  55478  dr. Jelena Sedlar  Matematika  Raziskovalec  2023 - 2024  40 
22.  36239  dr. Roman Sotak  Matematika  Raziskovalec  2022 - 2024  62 
23.  15518  dr. Riste Škrekovski  Matematika  Vodja  2021 - 2024  518 
24.  53598  dr. Kenny Štorgel  Matematika  Mladi raziskovalec  2022 - 2024  22 
25.  23904  dr. Aleksandra Tepeh  Matematika  Raziskovalec  2022 - 2024  132 
26.  30920  dr. Janoš Vidali  Matematika  Raziskovalec  2021 - 2024  26 
27.  14273  dr. Arjana Žitnik  Matematika  Raziskovalec  2021 - 2024  103 
Organizacije (4)
š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.552 
2.  2547  Univerza v Mariboru, Fakulteta za naravoslovje in matematiko  Maribor  5089638051  18.165 
3.  2784  Fakulteta za informacijske študije v Novem mestu  Novo mesto  3375650  6.191 
4.  2790  Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije  Koper  1810014009  17.909 
Povzetek
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 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 3 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čkam Fanove ravnine dodeljujejo povezavam kubičnega grafa tako, da so barve vsakih treh povezav s skupnim krajiščem tvorijo premico. Eden od ciljev naše raziskave je nadaljevanje študij o najmanjšem številu premic, ki se pojavijo kot barvni vzorci okoli vozlišč. V tem smislu je Fanovo barvanje z 1 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.
Zgodovina ogledov
Priljubljeno