1. Tree-independence number of ▫$P_5$▫-free graphs with no large bicliquesVáclav Blažej, J. Pascal Gollin, Tomáš Hons, Tomáš Masařík, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, Alexandra Wesolek, 2026, objavljeni znanstveni prispevek na konferenci Opis: The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique K_{t,t} forces tree-independence number at least t. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers s and t, {P_s,K_{t,t}}-free graphs have bounded tree-independence number. We prove this conjecture for s = 5 by showing that every {P₅,K_{t,t}}-free graph has tree-independence number at most 4t. We also obtain related bounds for the weaker parameter of independence degeneracy.
Ključne besede: tree-independence number, independence degeneracy, independence treewidth, P5-free graphs
Objavljeno v RUP: 21.09.2026; Ogledov: 274; Prenosov: 5
 Celotno besedilo (1,00 MB)
Gradivo ima več datotek! Več... |
2. Induced matching treewidth and tree-independence number, revisitedNoga Alon, Martin Milanič, Paweł Rzążewski, 2026, izvirni znanstveni članek Opis: We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with respect to different measures of a tree decomposition T of a graph G: for tree-independence number, the measure is the maximum size of an independent set in G included in some bag of T, while for the induced matching treewidth, the measure is the maximum size of an induced matching in G such that some bag of T contains at least one endpoint of every edge of the matching. While the induced matching treewidth of any graph is bounded from above by its tree-independence number, the family of complete bipartite graphs shows that small induced matching treewidth does not imply small tree-independence number. On the other hand, Abrishami, Briański, Czyżewska, McCarty, Milanič, Rzążewski, and Walczak [SIAM Journal on Discrete Mathematics, 2025] showed that, if a fixed biclique K_{t,t} is excluded as an induced subghraph, then the tree-independence number is bounded from above by some function of the induced matching treewidth. The function resulting from their proof is exponential even for fixed t, as it relies on multiple applications of Ramsey’s theorem. In this note we show, using the Kövári-Sós-Turán theorem, that for any class of K_{t,t}-free graphs, the two parameters are in fact polynomially related.
Ključne besede: tree-independence number, induced matching treewidth, induced biclique, Kövári-Sós-Turán theorem
Objavljeno v RUP: 17.09.2026; Ogledov: 280; Prenosov: 6
Celotno besedilo (471,21 KB)
Gradivo ima več datotek! Več... |
3. Treewidth versus clique number. v. further connections with tree‐independence numberClaire Hilaire, Martin Milanič, Ðorđe Vasić, 2026, izvirni znanstveni članek 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: 881; Prenosov: 17
Celotno besedilo (1,87 MB)
Gradivo ima več datotek! Več... |
4. Induced minor models : Structural properties and algorithmic consequencesNicolas Bousquet, Clément Jean Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, Nicolas Trotignon, 2026, izvirni znanstveni članek Opis: A graph H is an induced minor of G if there exists an induced minor model of H in G, that is, a collection of pairwise disjoint subsets of vertices of G labeled by the vertices of H, each inducing a connected subgraph in G, such that two vertices of H are adjacent if and only if there is an edge in G between the corresponding subsets. In this paper, we investigate structural properties of induced minor models, including bounds on treewidth and chromatic number of the subgraphs induced by minimal induced minor models. As algorithmic applications of our structural results, we make use of recent developments regarding tree-independence number to show that if H is the 4-wheel, the 5-vertex complete graph minus an edge, or a complete bipartite graph K2,q , then there is a polynomial-time algorithm to find in a given graph G an induced minor model of H in G, if there is one. We also develop an alternative polynomial-time algorithm for recognizing graphs that do not contain K2,3 as an induced minor, which revolves around the idea of detecting the induced subgraphs whose presence is forced when the input graph contains K2,3 as an induced minor. It turns out that all these induced subgraphs are Truemper configurations.
Ključne besede: induced minor, treewidth, chromatic number, tree-independence number, Truemper configuration
Objavljeno v RUP: 16.12.2025; Ogledov: 1260; Prenosov: 10
Celotno besedilo (1,44 MB)
Gradivo ima več datotek! Več... |
5. On relationships between treewidth, clique number, tree-independence number, and induced minors : master’s thesisÐorđe Vasić, 2025, magistrsko delo Ključne besede: treewidth, clique number, tree-independence number, induced minor, hered itary graph class, bipartite chain graph
Objavljeno v RUP: 11.09.2025; Ogledov: 1753; Prenosov: 39
Celotno besedilo (839,36 KB) |
6. |
