treewidth
integer invariant of an undirected graph which measures how far it is from being a tree
Facts
7 properties- Instance of
- graph property
- Defining formula
- \operatorname{tw}(G)=\min\{\omega(H)-1\mid H\supseteq G, H\text{ chordal}\}
- Discoverer or inventor
- Francesco Brioschi, Rudolf Halin, Neil Robertson, Paul Seymour[2][3][4][5]
- Greater than
- degeneracy, chordality, cop number[7][8][9]
- In defining formula
- \operatorname{tw}, \omega, H\supseteq G, H
- Less than
- circumference, pathwidth, feedback vertex set number, carving width, branchwidth, positive semidefinite zero forcing number[10][11][12][13][14][15]
- Studied by
- graph theory[6]
🏷️ Also known as
en tree-width
en treewidth
en tw(G)
de Baumweite
fa عرض درخت
fr largeur arborescente
hu favastagság
hu faszélesség
hu minimális fafelbontás szélessége
ja 木幅
ru древовидная ширина
uk деревна ширина
zh 树宽
zh 樹寬值
zh 樹闊
🔖 Identifiers · 6
- OpenAlex ID
- C132569581
- Freebase ID
- /m/0r4rwn3
- Graphclasses.org ID
- par_10
- MathWorld ID
- Treewidth
- Microsoft Academic ID (discontinued)
- 132569581
- Stack Exchange tag
- cstheory.stackexchange.com, cs.stackexchange.com
🔗 Connections
← Less than 5
Discoverer or inventor 4
← Has characteristic 2
Greater than 1
Instance of 1
Less than 1
Maintained by WikiProject 1
Studied by 1
← Greater than 1
Press Enter · cited answer in seconds
0 sources
Summary
treewidth is a graph property[1].