Sodobne invariante grafov

ARRS št. projekta J1-9109

O projektu

Trajanje projekta

1. 7. 2018 – 30. 6. 2021

Financer

Vsebinski opis projekta

Več informacij

Teorija grafov je hitro rastoče področje sodobne matematike in obravnava invariant grafov njen inherenten sestavni del. V tem projektu obravnavamo nekatere probleme, ki zadevajo klasične koncepte teorije grafov in njihovo obravnavo na naraven način kombiniramo s študijami nedavno vpeljanih in pogosto uporabnih grafovskih parametrov. Nekatere od novejših invariant, ki jih obravnavamo, so bile motivirane s praktičnimi problemi in aplikacijami, druge pa so bile vpeljane ob iskanju orodij za naskok na pomembne odprte domneve. Obravnavane invariante lahko razdelimo na več tipov in sicer, invariante barvanj, dominacijske invariante, invariante pokritij, dimenzijske invariante in igralne invariante grafov.

Glavni cilji projekta so:

  1. Podati nov vpogled in po možnosti tudi rešiti znamenite odprte probleme in domneve. Raziskave bodo vključevale variacije dominantnih števil kartezičnega produkta grafov (Vizingova domneva in rezultati Vizingovega tipa), kromatično število direktnega produkta grafov (Hedetniemijeva domneva), L(2,1) barvanja grafov z omejeno stopnjo (domneva Grigga in Yeha), b-kromatično število regularnih grafov (domneva Erdős-Farber-Lovász), dominantno število ravninskih skoraj triangulacij (domneva Mathesona in Tarjana), vozliščno pokritje k-poti v ravninskih grafih (šibka verzija Albertson-Bermanove domneve), pokritje grafa z geodetskimi potmi (povezava z Meynielovo domnevo), domneve o igralnem (celotnem) dominantnem številu, odprti problemi o igralnem kromatičnem številu in njegovih variacijah.
  2. Nadaljevati raziskave nekaterih nedavno vpeljanih invariant grafov in prispevati pomemben napredek pri njihovi obravnavi. Invariante vključujejo, a niso omejene na različna barvanja in (mavrične) dominacijske invariante, b-kromatična števila, (sproščena) L(j,k) označevanja, pakirno kromatično število, različice invariant pokritij (še posebej omenimo vozliščno pokritje k-poti in krepko geodetsko število), različne tipe metrične dimenzije grafov in invariante, ki izhajajo iz iger na grafih kot npr. igralno kromatično število, indicirano kromatično število, igralno Grundyjevo število in igralno (celotno) dominantno število.
  3. Prispevati celovite študije nekaterih med seboj prepletenih konceptov, ki bodo rezultirale v vsaj dveh preglednih člankih. V teh člankih nameravamo identificirati in poudariti osrednje odprte probleme kot tudi zastaviti nove odprte probleme. Pričakujemo, da bodo takšni pregledni članki imeli velik vpliv na pripadajoča raziskovalna področja. Osredotočili se bomo na več področij:
    1. dominacijske igre, za katere načrtujemo napisati monografijo;
    2. pakirna barvanja in sorodni koncepti barvanj, porojeni z razdaljami v grafu;
    3. invariante dominacijskega tipa in njihovo vedenje v kartezičnem produktu grafov
      (rezultati Vizingovega tipa).
  4. V načrtu tega projekta je monografija, ki bo obravnavala dominacijsko igro in sorodne igre ter invariante. Ta igra je bila vpeljana leta 2010 in je že v tem času postala ena najbolj široko obravnavanih iger na grafih. Pri pisanju knjige bosta sodelovala dva člana projektne skupine ter dva zunanja sodelavca, pri čemer smo bili vsi vključeni v raziskave dominacijske igre od samega začetka.

Projektna skupina

Več informacij
Ime in priimek Vloga Šifra raziskovalca Inštitucija
dr. Boštjan Brešar vodja projekta 17005 FNM UM, IMFM
dr. Aleksander Vesel raziskovalec 11666 FNM UM
dr. Petra Žigert Pleteršek raziskovalka 18504 FNM UM
dr. Tadeja Kraner Šumenjak raziskovalka 22648 FNM UM
dr. Andrej Taranenko raziskovalec 21821 FNM UM
dr. Marko Jakovac raziskovalec 29919 FNM UM
dr. Polona Repolusk raziskovalka 32250 FNM UM
dr. Niko Tratnik raziskovalec 37537 FNM UM
Aleksander Kelenc raziskovalec 37839 FNM UM
Jasmina Ferme raziskovalka 50186 FNM UM
dr. Bojan Mohar raziskovalec 01931 IMFM
dr. Sandi Klavžar raziskovalec 05949 IMFM
dr. Sergio Cabello Justo raziskovalec 25993 IMFM
dr. Iztok Peterin raziskovalec 20839 IMFM
dr. Simon Špacapan raziskovalec 24904 IMFM
dr. Tilen Marc raziskovalec 37403 IMFM