20.500.12556/RUP-22851 Excluding an induced wheel minor in graphs without large induced stars We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer d and any planar graph H, the class of all K_{1,d}-free graphs without H as an induced minor has bounded tree-independence number. A k-wheel is the graph obtained from a cycle of length k by adding a vertex adjacent to all vertices of the cycle. We show that the conjecture of Dallard et al. is true when H is a k-wheel for any k at least 3. Our proof uses a generalization of the concept of brambles to tree-independence number. As a consequence of our main result, several important NP-hard problems such as Maximum Independent Set are tractable on K_{1,d}-free graphs without large induced wheel minors. Moreover, for fixed d and k, we provide a polynomial-time algorithm that, given a K_{1,d}-free graph G as input, finds an induced minor model of a k-wheel in G if one exists. 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. induced minor wheel tree-independence number Maximum Independent Set induciran minor kolo drevesno neodvisnostno število problem največje neodvisne množice true false false Angleški jezik Slovenski jezik Neznano 2026-03-25 09:58:25 2026-03-25 09:58:26 2026-03-26 03:08:57 0000-00-00 00:00:00 2026 0 0 Str. 135-148 0000-00-00 Zaloznikova NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 2027-01-01 519.17 0302-9743 272877059 10.1007/978-3-032-11835-6_10 272882435 https://link.springer.com/chapter/10.1007/978-3-032-11835-6_10 1 c384fd9f-2828-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33342 https://arxiv.org/abs/2506.08829 1 c438a1ee-2828-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33343 RAZ_Choi_Mujin_2026.pdf RAZ_Choi_Mujin_2026.pdf 1 5A6F5D1AE81D14AF440B21DD35847C71 7e98c4ae07c6de97fb73d1755c9ffc5aaf234787b7c282d51333fffe74dfdb82 19e80334-2829-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33344 Fakulteta za matematiko, naravoslovje in informacijske tehnologije 0 0 0