{"schema_version":"4ort.packet/1","entity":{"entity_id":"treewidth","kg_uuid":"769f8f4f-6336-4223-a9bc-0b567648a3a2","wikidata_id":"Q5067368","name":"treewidth","description":"integer invariant of an undirected graph which measures how far it is from being a tree","type":"Thing","url":"https://4ort.xyz/entity/treewidth"},"status":"complete","as_of":{"copy_written_at":"2026-11-17T15:31:47Z","last_source_edit_seen":"2026-10-08T07:48:06Z","stale_possible":true,"claims_refreshed_at":null,"source_revision":null},"facts":[{"field":"P31","label":"instance of","value":"graph property","value_id":"Q722659","value_raw":"Q722659","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P31","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Francesco Brioschi","value_id":"Q737414","value_raw":"Q737414","rank":"normal","current":null,"qualifiers":[{"field":"P575","label":"time of discovery or invention","value":"1972"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P61","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Rudolf Halin","value_id":"Q7377197","value_raw":"Q7377197","rank":"normal","current":null,"qualifiers":[{"field":"P575","label":"time of discovery or invention","value":"1976"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P61","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Neil Robertson","value_id":"Q1531456","value_raw":"Q1531456","rank":"normal","current":null,"qualifiers":[{"field":"P575","label":"time of discovery or invention","value":"1984"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P61","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Paul Seymour","value_id":"Q1396427","value_raw":"Q1396427","rank":"normal","current":null,"qualifiers":[{"field":"P575","label":"time of discovery or invention","value":"1984"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P61","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1482","label":"Stack Exchange tag","value":"https://cstheory.stackexchange.com/tags/treewidth","value_id":null,"value_raw":"https://cstheory.stackexchange.com/tags/treewidth","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P1482","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1482","label":"Stack Exchange tag","value":"https://cs.stackexchange.com/tags/treewidth","value_id":null,"value_raw":"https://cs.stackexchange.com/tags/treewidth","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P1482","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2534","label":"defining formula","value":"\\operatorname{tw}(G)=\\min\\{\\omega(H)-1\\mid H\\supseteq G, H\\text{ chordal}\\}","value_id":null,"value_raw":"\\operatorname{tw}(G)=\\min\\{\\omega(H)-1\\mid H\\supseteq G, H\\text{ chordal}\\}","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P2534","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"https://11011110.github.io/blog/2012/11/15/graph-parameters-and.html","title":"Graph parameters and cliques in supergraphs"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2579","label":"studied by","value":"graph theory","value_id":"Q131476","value_raw":"Q131476","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P2579","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2812","label":"MathWorld ID","value":"Treewidth","value_id":null,"value_raw":"Treewidth","rank":"normal","current":null,"qualifiers":[{"field":"P1810","label":"subject named as","value":"Treewidth"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P2812","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5135","label":"greater than","value":"degeneracy","value_id":"Q5251771","value_raw":"Q5251771","rank":"normal","current":null,"qualifiers":[{"field":"P1013","label":"criterion used","value":"greater than or equal to"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P5135","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"Girth and treewidth","stated_in_id":"Q131848296"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5135","label":"greater than","value":"chordality","value_id":"Q131931930","value_raw":"Q131931930","rank":"normal","current":null,"qualifiers":[{"field":"P1013","label":"criterion used","value":"greater than or equal to"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P5135","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"On the chordality of a graph","stated_in_id":"Q131932233"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5135","label":"greater than","value":"cop number","value_id":"Q48999572","value_raw":"Q48999572","rank":"normal","current":null,"qualifiers":[{"field":"P1011","label":"excluding","value":"disconnected graph"},{"field":"P1013","label":"criterion used","value":"greater than or equal to"},{"field":"P2534","label":"defining formula","value":"c(G)\\le\\lfloor\\operatorname{tw}(G)/2 + 1\\rfloor\\le\\operatorname{tw}(G)"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P5135","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"The cops and robber game on graphs with forbidden (induced) subgraphs","stated_in_id":"Q138827370"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5136","label":"less than","value":"circumference","value_id":"Q130377759","value_raw":"Q130377759","rank":"normal","current":null,"qualifiers":[{"field":"P1013","label":"criterion used","value":"less than"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P5136","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"Tree-width and circumference of graphs","stated_in_id":"Q130554490"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5136","label":"less than","value":"pathwidth","value_id":"Q7144893","value_raw":"Q7144893","rank":"normal","current":null,"qualifiers":[{"field":"P1013","label":"criterion used","value":"at most"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P5136","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"Defective and clustered colouring of graphs with given girth","stated_in_id":"Q130554279"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5136","label":"less than","value":"feedback vertex set number","value_id":"Q130480051","value_raw":"Q130480051","rank":"normal","current":null,"qualifiers":[{"field":"P1013","label":"criterion used","value":"upper-bounded by a function of"},{"field":"P2534","label":"defining formula","value":"\\operatorname{tw}(G) \\le \\operatorname{fvn}(G) + 1"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P5136","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"Defective and clustered colouring of graphs with given girth","stated_in_id":"Q130554279"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5136","label":"less than","value":"carving width","value_id":"Q118903356","value_raw":"Q118903356","rank":"normal","current":null,"qualifiers":[{"field":"P1013","label":"criterion used","value":"upper-bounded by a function of"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P5136","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"Comparing 17 graph parameters","stated_in_id":"Q130425378"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5136","label":"less than","value":"branchwidth","value_id":"Q130369404","value_raw":"Q130369404","rank":"normal","current":null,"qualifiers":[{"field":"P1013","label":"criterion used","value":"upper-bounded by a function of"},{"field":"P2534","label":"defining formula","value":"\\operatorname{tw}(G)\\le \\max\\left\\{\\left\\lfloor\\frac32\\beta(G)\\right\\rfloor, 2\\right\\}-1"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P5136","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"Graph minors. X. Obstructions to tree-decomposition","stated_in_id":"Q56001805"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6104","label":"maintained by WikiProject","value":"WikiProject Mathematics","value_id":"Q8487137","value_raw":"Q8487137","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P6104","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6366","label":"Microsoft Academic ID (discontinued)","value":"132569581","value_id":null,"value_raw":"132569581","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P6366","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P7235","label":"in defining formula","value":"\\operatorname{tw}","value_id":null,"value_raw":"\\operatorname{tw}","rank":"normal","current":null,"qualifiers":[{"field":"P9758","label":"symbol represents","value":"treewidth"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P7235","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P7235","label":"in defining formula","value":"\\omega","value_id":null,"value_raw":"\\omega","rank":"normal","current":null,"qualifiers":[{"field":"P9758","label":"symbol represents","value":"clique number"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P7235","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P7235","label":"in defining formula","value":"H\\supseteq G","value_id":null,"value_raw":"H\\supseteq G","rank":"normal","current":null,"qualifiers":[{"field":"P9758","label":"symbol represents","value":"supergraph"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P7235","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P7235","label":"in defining formula","value":"H","value_id":null,"value_raw":"H","rank":"normal","current":null,"qualifiers":[{"field":"P9758","label":"symbol represents","value":"chordal graph"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P7235","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P13104","label":"graphclasses.org ID","value":"par_10","value_id":null,"value_raw":"par_10","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5067368#P13104","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}}],"unknowns":[],"omitted":{"facts":0,"reason":null},"licences":[{"source":"wikidata","source_name":"Wikidata","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"fields":["P31","P61","P1482","P2534","P2579","P2812","P5135","P5136","P6104","P6366","P7235","P13104"]}],"routes":{"entity_page":"https://4ort.xyz/entity/treewidth","packet_api":"https://4ort.xyz/api/v1/entities/treewidth/packet","facts_jsonld":"https://4ort.xyz/entity/treewidth/facts.json","changes_api":"https://4ort.xyz/api/v1/knowledge/get_entity_changes?entity=treewidth","attention_api":"https://4ort.xyz/api/v1/knowledge/get_attention?entity=treewidth","wikidata":"https://www.wikidata.org/wiki/Q5067368","official_website":null},"trust_rules":{"wikidata-reference-support/2":"From the references in our copy of the statement: high = it cites a source (stated in P248, or a reference URL that is not Wikipedia); medium = only 'imported from Wikimedia project' or a Wikipedia URL; unscored = our copy holds no reference (older copies dropped references, so this is not evidence that Wikidata has none). Wikidata may hold more references than our copy shows. Reference support, not a probability."},"notes":["Our copy of this item's statements has not been checked against Wikidata since tracking began (2026-10-25); a newer value may exist."]}