20.500.12556/RUP-22939 Treewidth versus clique number. v. further connections with tree‐independence number We continue the study of (tw, ω)‐bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation of this property to boundedness of the tree‐independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2024. Dallard et al. showed that bounded tree‐independence number is sufficient for (tw, ω)‐boundedness, and conjectured that the converse holds. While this conjecture has been recently disproved, it is still interesting to determine classes where the conjecture holds; for example, the conjecture is still open for graph classes excluding an induced star, as well as for finitely many forbidden induced subgraphs. In this paper, we identify further families of graph classes where (tw, ω)‐boundedness is equivalent to bounded tree‐independence number. We settle a number of cases of finitely many forbidden induced subgraphs, obtain several equivalent characterizations of (tw, ω)-boundedness in subclasses of the class of complements of line graphs, and give a short proof of a recent result of Ahn, Gollin, Huynh, and Kwon [SODA 2025] establishing bounded tree-independence number for graphs excluding a fixed induced star and a fixed number of independent cycles. V članku nadaljujemo s preučevanjem (tw, ω)-omejenih razredov grafov, torej hereditarnih razredov grafov, v katerih je za veliko drevesno širino odgovorna prisotnost velike klike, in razmerjem te lastnosti do omejenosti drevesnega neodvisnostnega števila, invariante grafov, ki so jo neodvisno uvedli Yolov leta 2018 ter Dallard, Milanič in Štorgel leta 2024. Dallard in sodelavci so pokazali, da je omejeno drevesno neodvisnostno število zadosten pogoj za (tw, ω)-omejenost, in postavili domnevo, da je pogoj tudi potreben. Čeprav je bila ta domneva nedavno ovržena, je še vedno zanimivo določiti razrede, kjer domneva velja; domneva je na primer še vedno odprta za razrede grafov, ki izključujejo neko fiksno inducirano zvezdo, kot tudi za končno število prepovedanih induciranih podgrafov. V tem članku identificiramo nadaljnje družine grafovskih razredov, kjer je (tw, ω)-omejenost enakovredna omejenemu drevesnemu neodvisnostnemu številu. Rešili smo številne primere za končno mnogo prepovedanih induciranih podgrafov, izpeljali več enakovrednih karakterizacij (tw, ω)-omejenosti v podrazredih razreda komplementov povezavnih grafov in podali kratek dokaz nedavnega rezultata Ahna, Gollina, Huynha in Kwona [SODA 2025], ki podaja omejenost drevesnega neodvisnostnega številega za grafe, ki izključujejo neko fiksno inducirano zvezdo in fiksno število paroma neodvisnih ciklov. clique number hereditary graph class line graph tree‐independence number treewidth klično število hereditaren razred grafov povezaven graf drevesno neodvisnostno število drevesna širina true false true Angleški jezik Slovenski jezik Članek v reviji 2026-04-09 09:00:48 2026-04-09 09:00:52 2026-04-10 03:09:11 0000-00-00 00:00:00 2026 0 0 str. 1-15 iss. Vol. 2026 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2026-04-08 519.17 0364-9024 10.1002/jgt.70036 274621699 RAZ_Hilaire_Claire_2026.pdf RAZ_Hilaire_Claire_2026.pdf 1 56C4F2BC82B6F82A9483D2D2142D80D3 875397c1fe4609e101c0cc7947a5efa44872ba15e200e32fe299ca3b8f59b84d f8c5b366-33e1-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33504 https://onlinelibrary.wiley.com/doi/10.1002/jgt.70036 1 cd2c482e-33e1-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33503 Inštitut Andrej Marušič Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije 0 0 0