Tree-Independence Number

The tree-independence number of a graph is the minimum, over its tree decompositions, of the largest independence number of the induced subgraphs on the bags. In symbols,

This replaces the bag-size measure underlying treewidth by the size of an independent vertex set (Dallard et al. 2024).

For a nonempty graph, the parameter is 1 iff the graph is a chordal graph. In particular, complete graphs have tree-independence number 1 even though their treewidth is unbounded. The tree-independence number is at most the treewidth plus 1.

If has no induced complete bipartite graph and has induced matching treewidth at most , then

for each fixed positive integer (Alon et al. 2026). Thus these two parameters are polynomially related under the stated exclusion.