2025/10/16 by Maria Chudnovsky, Chudnovsky, Maria, E S Ajaykrishnan +3 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2510.15074
openalex publication_date 2025/10/16 · openalex created_date 2025/10/21 · openalex updated_date 2026/07/28
An independent set in a graph G is a set of pairwise non-adjacent vertices. A tree decomposition of G is a pair (T, χ) where T is a tree and χ: V(T) → 2V(G) is a function satisfying the following two axioms: for every edge uv ∈ V(G) there is a x ∈ V(T) such that \u,v\ ⊆ χ(x), and for every vertex u ∈ V(G) the set \x ∈ V(T) ~:~ u ∈ χ(X)\ induces a non-empty and connected subtree of T. The sets χ(x) for x ∈ V(T) are called the bags of the tree decomposition. The tree-independence number of G is the minimum taken over all tree decompositions of G of the maximum size of an independent set of the graph induced by a bag of the tree decomposition. The study of graph classes with bounded tree-independence number has attracted much attention in recent years, in part due its improtant algorithmic implications. A conjecture of Dallard, Milanič and Štorgel, connecting tree-independence number to the classical notion of treewidth, was one of the motivating problems in the area. This conjecture was recently disproved, but here we prove a slight variant of it, that retains much of the algorithmic significance. As part of the proof we introduce the notion of independence-containers, which can be viewed as a generalization of the set of all maximal cliques of a graph, and is of independent interest.