Drevesno neodvisnostno število grafov
natisniNaši preliminarni rezultati nakazujejo, da je drevesno neodvisnostno število pomemben dodatek v zbirko orodij v strukturni in algoritmični teoriji grafov. Ne tvori le skupne posplošitve drevesne širine in tetivnosti, ampak je povezano tudi s slavno domnevo Erdősa in Hajnala in s hitro razvijajočo se teorijo hi-omejenosti. Vse te motivacije vodijo do glavnega cilja predlaganega projekta: temeljite študije drevesnega neodvisnostnega števila, s končnim ciljem razvoja teorije te nove invariante grafov. Naš cilj je raziskati številna pomembna vprašanja, razdeljena na dve medsebojno povezani raziskovalni temi (Tema 1: temelji, Tema 2: izboljšave), vsaka z več podnalogami. Pričakujemo, da bo predlagan projekt dodatno utemeljil uporabnost drevesnega neodvisnostnega števila in z njim povezanih širinskih parametrov grafov, kar bo pripomoglo k povečanemu razumevanju strukturnih lastnosti (tw, omega)-omejenih razredov grafov in računske kompleksnosti različnih grafovskih optimizacijskih problemov na takih razredih.
