20.500.12556/RUP-23314 Graph classes closed under self-intersection A graph class is monotone if it is closed under taking subgraphs. A monotone class defined by finitely many obstructions has bounded treewidth if and only if one of the obstructions is a tripod, i.e. a disjoint union of subdivided claws and paths. This dichotomy also characterizes exactly those monotone graph classes for which many NP-hard graph problems admit polynomial-time algorithms. These dichotomies do not extend to the universe of all hereditary classes. This leads to the question of whether we can extend known dichotomies for monotone classes to larger families of hereditary classes. We answer this question affirmatively by considering the family of hereditary graph classes closed under self-intersection. This family is known to be located strictly between the monotone and hereditary classes. We prove a new structural characterization of graphs in self-intersection-closed classes excluding a tripod. In contrast to monotone classes excluding a tripod, these classes do not necessarily have bounded treewidth; in fact, they do not even need to be sparse. We use our characterization to give a complete dichotomy for Maximum Independent Set, and its weighted variant, on self-intersection-closed classes defined by finitely many obstructions: these problems are in P if the class excludes a tripod and NP-hard otherwise. Our dichotomy generalizes several known results on Maximum Independent Set in the literature. We also apply our characterization to obtain a dichotomy for Maximum Induced Matching on self-intersection-closed classes of bipartite graphs defined by finitely many obstructions, and for Satisfiability and Counting Satisfiability on self-intersection-closed classes of (bipartite) incidence graphs defined by finitely many obstructions. Finally, we use our characterization to obtain a dichotomy for boundedness of clique-width for self-intersection-closed classes of bipartite graphs defined by finitely many obstructions. Razred grafov je monoton, če je zaprt glede na podgrafe. Monoton razred, definiran s končno mnogo ovirami (prepovedanimi podgrafi), ima omejeno drevesno širino, če in samo če je ena od ovir stativ, tj. disjunktna ​​unija subdividiranih krempljev in poti. Ta dihotomija karakterizira tudi natanko tiste monotone razrede grafov, za katere mnogi NP-težki grafovski problemi dopuščajo polinomske algoritme. Te dihotomije se ne razširijo na univerzum vseh hereditarnih razredov, kar vodi do vprašanja, ali lahko znane dihotomije za monotone razrede razširimo na večje družine hereditarnih razredov. Na to vprašanje odgovorimo pritrdilno z obravnavo družine hereditarnih razredov grafov, zaprtih glede na samopreseke. Znano je, da se ta družina nahaja strogo med monotonimi in hereditarnimi razredi. Dokazujemo novo strukturno karakterizacijo grafov v razredih, zaprtih glede na samopreseke, brez stativa. V nasprotju z monotonimi razredi, ki izključujejo stativ, ti razredi nimajo nujno omejene drevesne širine; pravzaprav sploh niso nujno redki. Našo karakterizacijo uporabljamo za izpeljavo popolne dihotomije za problem največje neodvisne množice in njene utežene različice na samopresečno zaprtih razredih, definiranih s končnim številom ovir: ti problemi so v P, če razred izključuje stativ, in NP-težki sicer. Naša dihotomija posplošuje več znanih rezultatov o največji neodvisni množici v literaturi. Našo karakterizacijo uporabimo tudi za pridobitev dihotomije za problem največjega induciranega prirejanja na samopresečno zaprtih razredih dvodelnih grafov, definiranih s končnim številom ovir, ter za problem izpolnljivosti in preštevalno različico problema na samopresečno zaprtih razredih (dvodelnih) incidenčnih grafov, definiranih s končnim številom ovir. Nazadnje uporabimo našo karakterizacijo za pridobitev dihotomije za omejenost klične širine za samopresečno zaprte razrede dvodelnih grafov, definiranih s končnim številom ovir. graph classes self-intersection closed dichotomy independent set clique-width treewidth razred grafov zaprt glede na samopreseke dihotomija neodvisna množica klična širina drevesna širina true false true Angleški jezik Slovenski jezik Neznano 2026-07-15 08:34:28 2026-07-15 08:34:32 2026-07-16 03:06:59 0000-00-00 00:00:00 2026 0 0 Str. 14:1–14:15 0000-00-00 Zaloznikova NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2026-07-02 519.17 1868-8969 284815363 10.4230/LIPIcs.WG.2026.14 284824579 RAZ_Dabrowski_Konrad_K._2026.pdf RAZ_Dabrowski_Konrad_K._2026.pdf 1 DDA83B67DF90D4EC1C1EDAC76A12BBE3 b9ab88a9a5a253061383c2792787d5de9b85c97c75a9f21a952f4e802a7002bd 0dd76b36-8017-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=34088 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.14 0 3d279873-8017-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=34090 Fakulteta za matematiko, naravoslovje in informacijske tehnologije 0 0 0