treewidth

integer invariant of an undirected graph which measures how far it is from being a tree
Thing Graph Property Q5067368

Facts

7 properties
Instance of
graph property
Defining formula
\operatorname{tw}(G)=\min\{\omega(H)-1\mid H\supseteq G, H\text{ chordal}\}
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

Report an error or request removal Lineage (PROV-JSON)

🔗 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

Summary

treewidth is a graph property[1].

References

Programmatic citations — every numbered marker resolves to a verifiable graph row below.

Direct Wikidata claims

  1. [2] ↑ . wikidata.org.
  2. [3] ↑ . wikidata.org.
  3. [4] ↑ . wikidata.org.
  4. [5] ↑ . wikidata.org.
  5. [6] ↑ . wikidata.org.
  6. [7] ↑ . Girth and treewidth. wikidata.org.
  7. [8] ↑ . On the chordality of a graph. wikidata.org.
  8. [9] ↑ . The cops and robber game on graphs with forbidden (induced) subgraphs. wikidata.org.
  9. [10] ↑ . Tree-width and circumference of graphs. wikidata.org.
  10. [11] ↑ . Defective and clustered colouring of graphs with given girth. wikidata.org.
  11. [12] ↑ . Defective and clustered colouring of graphs with given girth. wikidata.org.
  12. [13] ↑ . Comparing 17 graph parameters. wikidata.org.
  13. [14] ↑ . Graph minors. X. Obstructions to tree-decomposition. wikidata.org.
  14. [15] ↑ . Parameters related to tree-width, zero forcing, and maximum nullity of a graph. wikidata.org.
  15. [16] ↑ . wikidata.org.

Class ancestry

  1. [1] ↑ . Wikidata. wikidata.org.

📑 Cite this page

Use these citations when quoting this entity in research, articles, AI prompts, or wherever provenance matters. We aggregate Wikidata + Wikipedia + authoritative open-data sources; the stitched, scored, cross-referenced view is what 4ort.xyz contributes.

APA 4ort.xyz Knowledge Graph. (2026). treewidth. Retrieved November 17, 2026, from https://4ort.xyz/entity/treewidth
MLA “treewidth.” 4ort.xyz Knowledge Graph, 4ort.xyz, 17 Nov. 2026, https://4ort.xyz/entity/treewidth.
BibTeX @misc{4ortxyz_treewidth_2026, author = {{4ort.xyz Knowledge Graph}}, title = {{treewidth}}, year = {2026}, url = {https://4ort.xyz/entity/treewidth}, note = {Accessed: 2026-11-17}}
LLM prompt According to 4ort.xyz Knowledge Graph (aggregator of Wikidata, Wikipedia, and authoritative open-data sources): treewidth — https://4ort.xyz/entity/treewidth (retrieved 2026-11-17)

Canonical URL: https://4ort.xyz/entity/treewidth · Last refreshed:

Edit History

Rolling log of changes to this entity's Wikidata record. Values shown reflect the current state of each edited property — follow the history link to see the precise diff for any edit.

  1. 5w ago · KrBot bot · 2026-10-08 view diff on Wikidata ↗
    Instance of → graph property
    Maintained by WikiProject → WikiProject Mathematics
    Less than → circumference, pathwidth, feedback vertex set number +1
    Studied by → graph theory
    + 2 other properties edited (see Wikidata diff for full list)
    "Changed qualifier: Criterion used: less than or equal to, разрешение перенаправления / resolving redirect less than or equal to → less than or equal to ()"
Live feed via Wikidata EventStreams. New edits appear within minutes of being made on Wikidata.