Iskanje po repozitoriju

Opis: 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.
Ključne besede: clique number, hereditary graph class, line graph, tree‐independence number, treewidth
Objavljeno v RUP: 09.04.2026; Ogledov: 321; Prenosov: 9
Celotno besedilo (1,87 MB)
Gradivo ima več datotek! Več...

Ključne besede: clique-width, power of a graph, hereditary graph class, power-bounded clique-width
Objavljeno v RUP: 03.04.2017; Ogledov: 4446; Prenosov: 158
Povezava na celotno besedilo

Ključne besede: price of connectivity, hereditary graph class, path, cycle, transversal
Objavljeno v RUP: 08.08.2016; Ogledov: 4477; Prenosov: 124
Povezava na celotno besedilo

Opis: Vizing's conjecture is true for graphs ▫$G$▫ satisfying ▫$\gamma^i(G) = \gamma(G)$▫, where ▫$\gamma(G)$▫ is the domination number of a graph ▫$G$▫ and ▫$\gamma^i(G)$▫ is the independence-domination number of ▫$G$▫, that is, the maximum, over all independent sets ▫$I$▫ in ▫$G$▫, of the minimum number of vertices needed to dominate ▫$I$▫. The equality ▫$\gamma^i(G) = \gamma(G)$▫ is known to hold for all chordal graphs and for chordless cycles of length ▫$0 \pmod{3}$▫. We prove some results related to graphs for which the above equality holds. More specifically, we show that the problems of determining whether ▫$\gamma^i(G) = \gamma(G) = 2$▫ and of verifying whether ▫$\gamma^i(G) \ge 2$▫ are NP-complete, even if ▫$G$▫ is weakly chordal. We also initiate the study of the equality ▫$\gamma^i = \gamma$▫ in the context of hereditary graph classes and exhibit two infinite families of graphs for which ▫$\gamma^i < \gamma$▫.
Ključne besede: Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph
Objavljeno v RUP: 15.10.2013; Ogledov: 5196; Prenosov: 134
Celotno besedilo (300,57 KB)