VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Excluding an induced wheel minor in graphs without large induced stars
    Choi, Mujin ...
    V prispevku preučujemo domnevo Dallarda, Krnca, Kwona, Milaniča, Munara, Štorgla in Wiederrechta, ki trdi, da ima za poljubno pozitivno celo število d in poljuben ravninski graf H razred vseh grafov ... brez inducirane zvezde K_{1,d} in brez induciranega minorja izomorfnega grafu H omejeno drevesno neodvisnostno število. Za celo število k vsaj 3 je k-kolo graf, ki ga dobimo iz cikla dolžine k z dodajanjem točke, ki sosednja vsem točkam cikla. Pokažemo, da domneva Dallarda idr. velja za primer, ko je H k-kolo za poljubno celo število k vsaj 3. Naš dokaz uporablja posplošitev koncepta trnjevja (ang. bramble) na drevesno neodvisnostno število. Posledica našega glavnega rezultata je, da je več pomembnih NP-težkih problemov, kot je največja neodvisna množica, polinomsko rešljivih na grafih brez inducirane fiksne zvezde in brez induciranih minorjev, izomorfnih nekemu fiksnemu kolesu. Poleg tega za fiksna d in k razvijemo polinomski algoritem, ki ob danem vhodnem grafu G brez inducirane zvezde K_{1,d} poišče model induciranega minorja za k-kolo v grafu G, če ta obstaja.
    Vir: Graph-theoretic concepts in computer science : 51st International Workshop, WG 2025 : Otzenhausen, Germany, June 11–13, 2025 : revised selected papers (Str. 135-148)
    Vrsta gradiva - prispevek na konferenci ; neleposlovje za odrasle
    Leto - 2026
    Jezik - angleški
    COBISS.SI-ID - 272882435

    Povezava(-e):

    https://link.springer.com/chapter/10.1007/978-3-032-11835-6_10
    https://arxiv.org/abs/2506.08829
    Repozitorij Univerze na Primorskem - RUP
    DOI

Vnos na polico