Hipergraf je 1-Spernerjev, če za vsaki dve hiperpovezavi najmanjša od obeh razlik hiperpovezav vsebuje natanko en element. V članku predstavimo številne uporabe 1-Spernerjevih hipergrafov na grafih. Najprej obravnavamo več načinov povezovanja hipergrafov z grafi, in sicer hipergrafe pokritij, klik, neodvisnih množic, dominantnih množic in zaprtih soseščin. Za vsakega izmed njih karakteriziramo grafe, ki porodijo 1-Spernerjeve hipergrafe. Tako dobimo nove karakterizacije pragovnih in dominantno pragovnih grafov. Nadalje, iz znane karakterizacije 1-Spernerjevih hipergrafov izpeljemo dekompozicijske izreke za dva razreda razcepljenih grafov, razred dvodelnih grafov in razred kodvodelnih grafov. Ti dekompozicijski izreki, ki temeljijo na nekaterih matričnih particijah, vodijo do novih razredov grafov omejene klične širine in do novih polinomsko rešljivih primerov treh osnovnih problemov dominacije: dominacije, celotne dominacije in povezane dominacije.
COBISS.SI-ID: 1541798340
Pravimo, da je razred grafov krotek, če imajo grafi v razredu število minimalnih separatorjev omejeno s polinomsko funkcijo števila točk grafa. Krotki razredi grafov imajo dobre algoritmične lastnosti, ki sledijo na primer iz algoritemskega metaizreka Fomina, Todince in Villangerja iz leta 2015. V članku dokažemo, da je hereditaren razred grafov X krotek, če in samo če je podrazred, sestavljen iz grafov v X brez kličnih prerezov, krotek. Ta rezultat in Ramseyev izrek vodita do več vrst zadostnih pogojev za krotkost razreda grafov. Pokažemo na primer, da je poljuben hereditaren razred grafov krotek, če ima omejeno klično prekrivno število in izključuje neko popolno prizmo, kjer je popolna prizma kartezični produkt polnega grafa s K_2. Te rezultate uporabimo v kombinaciji s konstrukcijami grafov z eksponentno mnogo minimalnimi separatorji, da razvijemo dihotomijski izrek, ki loči krotke od nekrotnih razredov grafov v družini razredov grafov, opredeljenih z množicami prepovedanih induciranih podgrafov z največ štirimi točkami.
COBISS.SI-ID: 57192963
Drevesna širina je pomembna invarianta grafov, relevantna tako iz strukturnih kot iz algoritmičnih razlogov. Nujen pogoj, da ima razred grafov omejeno drevesno širino, je odsotnost velikih klik. V prispevku preučujemo razrede grafov, pri katerih je ta pogoj tudi zadosten, ki jih imenujemo (tw, ?)-omejeni razredi. Znano je, da imajo takšni razredi grafov algoritmično uporabne lastnosti, povezane z različicami problemov klike in k-barvanja. Obravnavamo šest dobro znanih relacij vsebovanosti na grafih: minor, topološki minor, podgraf, induciran minor, induciran topološki minor in induciran podgraf. Za vsako od njih podamo popolno karakterizacijo grafov H, za katere je razred grafov brez H (tw, ?)-omejen. Naši rezultati kažejo, da je razred 1-popolno usmerljivih grafov (tw, ?)-omejen in s tem podaja odgovar na vprašanje Brešarja, Hartingerjeve, Kosa in Milaniča iz leta 2018. V članku razkrijemo tudi nekatere nadaljnje algoritemske posledice (tw, ?)-omejenosti, povezane s problemi seznamskega k-barvanja in klike.
COBISS.SI-ID: 36187651