Od pravilnih do krepkih barvanj povezav (Znanstvenoraziskovalno sodelovanje med R. Slovenijo in ZDA 2022-2024)
- 7 julija, 2022
- Katja Peterlin
- 0

Obdobje trajanja: 1. 7. 2022 – 30. 6. 2024
Naziv projekta: Od pravilnih do krepkih barvanj povezav
Sodeluje: Laboratorij za kompleksne sisteme in podatkovne znanosti
Vodja projekta: izr. prof. dr. Borut Lužar
Vrsta projekta: Bilateralni projekt
Kratek opis projekta:
Teorija grafov je mlada veja matematike. Njeni začetki segajo v 18. stoletje, ko je Euler postavil temelje z rešitvijo problema Kőnigsbergških mostov. Problem štirih barv, ki se je pojavil okrog leta 1852, je drugi široko prepoznaven problem teorije grafov. Potrebnih je bilo preko sto let za dokaz pozitivnega odgovora nanj. Problem je pritegnil znanstvenike z vseh področij matematike in prispeval k razvoju novih metod ne le v diskretni matematiki, temveč tudi v algebri, topologiji, računalništvu in drugih. Kromatična teorija grafov je še vedno ena izmed najpomembnejših vej teorije grafov, veji pa se na veliko število raziskovalnih smeri oziroma tipov problemov.
Osnovni problem v kromatični teoriji grafov je določitev najmanjšega števila barv, s katerimi lahko označimo vozlišča grafa tako, da imajo sosednja vozlišča različne barve. V splošnem, pa tudi v mnogih posebnih primerih, je problem NP-težek. S poznavanjem dodatnih strukturnih lastnosti, kot so na primer vložitve na ploskve, omejene minimalne stopnje ali prepovedane podstrukture, pa lahko problem poenostavimo. Skozi čas se je razvilo veliko število različic barvanj grafov, motiviranih tako s problemi iz vsakdanjega življenja kot tudi s teoretično uporabo. Med najbolj raziskovanimi so različni tipi barvanj povezav.
Projekt financira:
