樹寬

樹寬是衡量在最優樹分解中對映到任何樹頂點的原始圖頂點的數量的度量。確定任意圖的樹寬是一個 NP 難問題。然而，許多有界樹寬圖上的 NP 難問題可以在多項式時間內解決。

一個空圖的樹寬為 0，一個樹或森林的樹寬為 1，樹寬至多為 2 的圖對應於串並聯圖。每個Halin 圖的樹寬為 3 (Bodlaender 1988)。

非連通圖的樹寬等於其連通分量的樹寬的最大值。

樹寬為 的極大圖稱為 -樹，而樹寬 的圖被稱為部分 -樹。

樹寬 的圖可以用有限的停用次子圖集來表徵，如下表所示。對於 的情況，已知超過 75 個結構差異很大的最小停用次子圖 (Sanders 1993, Sanders 1995, Chlebiková 2002)。

樹寬界限	停用次子圖
1
2
3	, 八面體圖 , 稜柱圖 , 瓦格納圖
4	未知的有限數量的次子圖；至少已知 75 個

亂數是圖的度量（gonality）的最強大的已知下界，並且滿足

(1)

其中 是頂點連通度， 是邊連通度， 是亂數，而 是 的度量 (Harp et al. 2020, Echavarria et al. 2021)。

特殊情況包括

			(2)
			(3)
			(4)
			(5)
			(6)
			(7)
			(8)

其中 表示任何樹， 任何Halin 圖， 是一個迴圈圖， 是一個完全圖， 是一個完全二分圖，並且 是一個 網格圖。