{"entities":{"Q7276290":{"pageid":31084088,"ns":120,"title":"Item:Q7276290","lastrevid":104431216,"modified":"2026-07-10T19:39:27Z","type":"item","id":"Q7276290","labels":{"en":{"language":"en","value":"tree-depth"},"de":{"language":"de","value":"Baumtiefe"}},"descriptions":{"en":{"language":"en","value":"numerical invariant of graphs"},"de":{"language":"de","value":"ganzzahlige Graph-Invariante"}},"aliases":{"en":[{"language":"en","value":"td(G)"},{"language":"en","value":"treedepth"},{"language":"en","value":"minimum elimination tree height + 1"},{"language":"en","value":"upper chromatic number"},{"language":"en","value":"vertex ranking number"},{"language":"en","value":"centered chromatic number"},{"language":"en","value":"ordered chromatic number"}]},"claims":{"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c086e85cf64dc3a23164411236d660ef1b3f0654","datavalue":{"value":"Q7837500","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7276290$12FF262B-80CF-4389-B91C-CBEFF6C3D6BA","rank":"normal"}],"P373":[{"mainsnak":{"snaktype":"value","property":"P373","hash":"13558aa200663ccd47289c5bd886ced38e206a79","datavalue":{"value":"69284658","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7276290$4CC9EE14-3652-4135-B84E-D6433A504D76","rank":"normal"}],"P239":[{"mainsnak":{"snaktype":"value","property":"P239","hash":"c16767796bf8bab2cb6dd038c3380e4079dad4b0","datavalue":{"value":"/m/0kmpjr0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7276290$D8F03542-1099-4BF9-9867-6211FD34BA8C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ebafbc00fadad288aeaa8e20cef5b80ed762278f","datavalue":{"value":"C69284658","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7276290$2636AAB6-D7B0-4860-88D7-B4E4DDA47A90","rank":"normal","references":[{"hash":"b61840b5e4c07320c0aa508d1e9d37d18264ae22","snaks":{"P98":[{"snaktype":"value","property":"P98","hash":"d98ff3d8cd81c87263e3f0008a1ae470fbcf55ae","datavalue":{"value":{"entity-type":"item","numeric-id":56612,"id":"Q56612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}],"P69":[{"snaktype":"value","property":"P69","hash":"a8b2a7e9de45fd3832b36f489407e826769f65b6","datavalue":{"value":{"time":"+2022-01-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"}],"P56":[{"snaktype":"value","property":"P56","hash":"f7cf0fc8f94cea909ab2fa761ee0f84fb1ca5b1a","datavalue":{"value":"https://docs.openalex.org/download-snapshot/snapshot-data-format","type":"string"},"datatype":"url"}]},"snaks-order":["P98","P69","P56"]}]}],"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"9ca28b6a489c39abf672ed437d7b322bc8c5b03c","datavalue":{"value":{"entity-type":"item","numeric-id":7266493,"id":"Q7266493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7276290$4E2551DE-A94C-4C09-982C-D4E07E8775CB","rank":"normal"}],"P1192":[{"mainsnak":{"snaktype":"value","property":"P1192","hash":"a66977984a8dee97dc9bce9fc8e1a48de680d6dd","datavalue":{"value":"TreeDepth","type":"string"},"datatype":"external-id"},"type":"statement","qualifiers":{"P96":[{"snaktype":"value","property":"P96","hash":"0bf857a6723ad71695ed346bde6e720ca03437f8","datavalue":{"value":"Tree Depth","type":"string"},"datatype":"string"}]},"qualifiers-order":["P96"],"id":"Q7276290$00979F3E-FEE7-4828-8EB9-7A722A378AB0","rank":"normal"}],"P1956":[{"mainsnak":{"snaktype":"value","property":"P1956","hash":"9596024365972b36fea6044c2180ae284640ab0b","datavalue":{"value":{"entity-type":"item","numeric-id":7279512,"id":"Q7279512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P251":[{"snaktype":"value","property":"P251","hash":"e942e9cae3684de20f69ee8202f0bff0672a1b8b","datavalue":{"value":{"entity-type":"item","numeric-id":6480338,"id":"Q6480338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P251"],"id":"Q7276290$72E18870-6F03-4E3F-97E8-37B3004352C1","rank":"normal","references":[{"hash":"a2fa9d86622c40cf9964e880b5d665b0e14a5b90","snaks":{"P98":[{"snaktype":"value","property":"P98","hash":"13642ccb9d2e9e36c35b8064d8341811472994eb","datavalue":{"value":{"entity-type":"item","numeric-id":7279508,"id":"Q7279508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}],"P116":[{"snaktype":"value","property":"P116","hash":"7f1c53f857a79773c601380de0e2c7e9736af59b","datavalue":{"value":"Lemma 11","type":"string"},"datatype":"string"}]},"snaks-order":["P98","P116"]}]},{"mainsnak":{"snaktype":"value","property":"P1956","hash":"2bb5c197b66f37402c686e024eb73d318a69c40d","datavalue":{"value":{"entity-type":"item","numeric-id":7279511,"id":"Q7279511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P251":[{"snaktype":"value","property":"P251","hash":"3951b2472464a1862d183418678477a8be2b51a5","datavalue":{"value":{"entity-type":"item","numeric-id":7265939,"id":"Q7265939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P251"],"id":"Q7276290$4B85C859-E894-4A01-98F2-03AC637097F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1956","hash":"cf783c43d8c6f6ced093b4255ce6ce1d944175a5","datavalue":{"value":{"entity-type":"item","numeric-id":7282244,"id":"Q7282244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P251":[{"snaktype":"value","property":"P251","hash":"3951b2472464a1862d183418678477a8be2b51a5","datavalue":{"value":{"entity-type":"item","numeric-id":7265939,"id":"Q7265939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P251"],"id":"Q7276290$C2D442DF-C9CE-4CA4-ADE5-5DCF7CF9CBC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1956","hash":"cafd70820b664d691fc4159ad7a278bd3aa1175f","datavalue":{"value":{"entity-type":"item","numeric-id":7271516,"id":"Q7271516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P251":[{"snaktype":"value","property":"P251","hash":"3951b2472464a1862d183418678477a8be2b51a5","datavalue":{"value":{"entity-type":"item","numeric-id":7265939,"id":"Q7265939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P251"],"id":"Q7276290$92A6DFF2-A847-41A0-B712-771EFC667A73","rank":"normal"}],"P1679":[{"mainsnak":{"snaktype":"value","property":"P1679","hash":"6adda491a37ef9044294847475145081632a3aaf","datavalue":{"value":"par_18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7276290$0BDBCD93-D6FD-4F27-ACE4-4BBFB9EF9CA3","rank":"normal"}],"P1958":[{"mainsnak":{"snaktype":"value","property":"P1958","hash":"11e480f565bdc53f27063dce1cc2f2af78be58d1","datavalue":{"value":{"entity-type":"item","numeric-id":7274332,"id":"Q7274332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P251":[{"snaktype":"value","property":"P251","hash":"7ee9b0ac9fd07736dbf4f3726bfb37d9887354c8","datavalue":{"value":{"entity-type":"item","numeric-id":7266236,"id":"Q7266236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P251"],"id":"Q7276290$107CA42E-6CB7-48A6-B32F-F1EF07BDF27C","rank":"normal","references":[{"hash":"d5724049eddf15b85f7bcf84a657c1ef032b9450","snaks":{"P98":[{"snaktype":"value","property":"P98","hash":"ae35b89785a9799494354092a170b1d7fa184316","datavalue":{"value":{"entity-type":"item","numeric-id":7282245,"id":"Q7282245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}],"P116":[{"snaktype":"value","property":"P116","hash":"fa0ce5c4c745de4c589c42afa7d13ebe4193d475","datavalue":{"value":"Proposition 6.1","type":"string"},"datatype":"string"}],"P220":[{"snaktype":"value","property":"P220","hash":"837ed51160791042a87cbf460f27170e50a5ffa5","datavalue":{"value":{"text":"Assume G includes no path of order greater than n. Then the tree-depth of G is at most n.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"}]},"snaks-order":["P98","P116","P220"]}]},{"mainsnak":{"snaktype":"value","property":"P1958","hash":"72c16ffe234d0da53db07e7d7dd9670b98042a76","datavalue":{"value":{"entity-type":"item","numeric-id":6672199,"id":"Q6672199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P251":[{"snaktype":"value","property":"P251","hash":"5ca1819e695d4cc7e5ef7516d029bad09bfc6992","datavalue":{"value":{"entity-type":"item","numeric-id":7274336,"id":"Q7274336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}],"P989":[{"snaktype":"value","property":"P989","hash":"0a198a6999aa39bf2fb6f10272301f8b03668d13","datavalue":{"value":"\\operatorname{td}(G) \\le \\operatorname{vc}(G) + 1","type":"string"},"datatype":"math"}]},"qualifiers-order":["P251","P989"],"id":"Q7276290$703F7EA9-FEBE-451F-B3FA-D06EEAB142A2","rank":"normal","references":[{"hash":"540623b93648bc651b03d8e7ef32251c4c70bb6a","snaks":{"P98":[{"snaktype":"value","property":"P98","hash":"6bc1f147a4137bb9b2d9226d30391630a81f20cf","datavalue":{"value":{"entity-type":"item","numeric-id":7282246,"id":"Q7282246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}],"P220":[{"snaktype":"value","property":"P220","hash":"f89daa1aae3eaf5c374e013050b3c20cd9714b7d","datavalue":{"value":{"text":"It is known that tw(G) \u2264 pw(G) \u2264 td(G) \u2212 1 \u2264 vi(G) \u2212 1 \u2264 vc(G) for every graph G","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"}]},"snaks-order":["P98","P220"]}]}],"P989":[{"mainsnak":{"snaktype":"value","property":"P989","hash":"63430f497fbde0e875b5947e76be980a2297326f","datavalue":{"value":"\\operatorname{td}(G)=\\begin{cases} 1, & \\text{if }|G|=1\\\\ 1 + \\min_{v\\in V} \\operatorname{td}(G-v), & \\text{if } G \\text{ is connected and } |G| > 1\\\\ \\max_{i} \\operatorname{td}(G_i), & \\text{otherwise} \\end{cases}","type":"string"},"datatype":"math"},"type":"statement","id":"Q7276290$548B2643-94E9-4E02-A1AD-432E868A3CDE","rank":"normal","references":[{"hash":"edffbc1d431c162887ba69073326765a8c9c4d35","snaks":{"P50":[{"snaktype":"value","property":"P50","hash":"1af612a669661b558180abb2d89e1425e7c74913","datavalue":{"value":"https://en.wikipedia.org/w/index.php?title=Tree-depth&oldid=1234817635#Definitions","type":"string"},"datatype":"url"}]},"snaks-order":["P50"]}]},{"mainsnak":{"snaktype":"value","property":"P989","hash":"f2d2918536dc1d4cea0935217650891de88bb7e5","datavalue":{"value":"\\operatorname{td}(G)=\\min\\{\\omega(H)\\mid H\\supseteq G, H\\text{ trivially perfect}\\}","type":"string"},"datatype":"math"},"type":"statement","id":"Q7276290$CAFA2697-5809-43A7-A56B-DDFD8EFD9F7A","rank":"normal","references":[{"hash":"3b8d41d7755c1119d19f913e7fc5abc09b8a4da0","snaks":{"P56":[{"snaktype":"value","property":"P56","hash":"2a0ece3e54c91ec81c7022cf273b2aaf757f56a1","datavalue":{"value":"https://11011110.github.io/blog/2012/11/15/graph-parameters-and.html","type":"string"},"datatype":"url"}],"P159":[{"snaktype":"value","property":"P159","hash":"7eb0fe874e4d90475e505369d98bbdf174df394d","datavalue":{"value":{"text":"Graph parameters and cliques in supergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"}],"P16":[{"snaktype":"value","property":"P16","hash":"c957339beeae6f46596c701e650eab7f54dbbfce","datavalue":{"value":{"entity-type":"item","numeric-id":283880,"id":"Q283880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"snaks-order":["P56","P159","P16"]}]}],"P983":[{"mainsnak":{"snaktype":"value","property":"P983","hash":"c7c10ea259af6e8df349048f3119f23edda1ae99","datavalue":{"value":"\\operatorname{td}","type":"string"},"datatype":"math"},"type":"statement","qualifiers":{"P984":[{"snaktype":"value","property":"P984","hash":"3353d92c37a2a1d2d8124695feae8a29c5eb1b47","datavalue":{"value":{"entity-type":"item","numeric-id":7276290,"id":"Q7276290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P984"],"id":"Q7276290$EFB5E193-1C5A-4BC7-89DD-1F1CA32C09C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P983","hash":"f21c4470662fe248aba3c6b332bd2fc9719f81c0","datavalue":{"value":"|G|","type":"string"},"datatype":"math"},"type":"statement","qualifiers":{"P984":[{"snaktype":"value","property":"P984","hash":"0d55f21bfd9789cfbe96382e7ef9ad3092250de2","datavalue":{"value":{"entity-type":"item","numeric-id":6822370,"id":"Q6822370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P984"],"id":"Q7276290$7AF00BEC-06D4-42A9-B829-2CA9F7F74594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P983","hash":"79d38cafe3f15d673eed06fafb2fdb38147186e0","datavalue":{"value":"G_i","type":"string"},"datatype":"math"},"type":"statement","qualifiers":{"P984":[{"snaktype":"value","property":"P984","hash":"998b88add47b192001ea99916e979fa59bd33815","datavalue":{"value":{"entity-type":"item","numeric-id":7271940,"id":"Q7271940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P984"],"id":"Q7276290$560E9DD6-A03B-46DC-AB4A-5C572E0EA1BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P983","hash":"e13ad2644e10bba88b4abb3fa1d8e74ad1e7b0aa","datavalue":{"value":"V","type":"string"},"datatype":"math"},"type":"statement","qualifiers":{"P984":[{"snaktype":"value","property":"P984","hash":"c4d77b9e8ad1dea40632f08f09ff06b5e27c48af","datavalue":{"value":{"entity-type":"item","numeric-id":6674074,"id":"Q6674074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P984"],"id":"Q7276290$5F3A867B-8689-452E-A01F-51CFE63D7E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P983","hash":"a28ff539da71afa7875314e9827e5ff0e6367eaf","datavalue":{"value":"\\omega","type":"string"},"datatype":"math"},"type":"statement","qualifiers":{"P984":[{"snaktype":"value","property":"P984","hash":"5ba9f8d6108623f9a5ed752de3e3f6b3bc0a33eb","datavalue":{"value":{"entity-type":"item","numeric-id":7276292,"id":"Q7276292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P984"],"id":"Q7276290$4D5B41C0-81D1-45DC-ABF4-DB3A134BB700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P983","hash":"e00fb48045bd4e884d2b3c9e335bdcdfea1b9f94","datavalue":{"value":"H\\supseteq G","type":"string"},"datatype":"math"},"type":"statement","qualifiers":{"P984":[{"snaktype":"value","property":"P984","hash":"d6fcf5809a94e629214bc3be50898e6b75fb1a89","datavalue":{"value":{"entity-type":"item","numeric-id":7279513,"id":"Q7279513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P984"],"id":"Q7276290$D1628C8D-3107-4275-8025-A75E4293107A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P983","hash":"bb969f09cf2a9a9c95e3a58307dd18e7daacbc20","datavalue":{"value":"H","type":"string"},"datatype":"math"},"type":"statement","qualifiers":{"P984":[{"snaktype":"value","property":"P984","hash":"90f41ccde807bb36f6af06ea3f70ff8fa7f218d8","datavalue":{"value":{"entity-type":"item","numeric-id":7282247,"id":"Q7282247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P984"],"id":"Q7276290$CD383223-985F-4D38-803A-A3C6113F8754","rank":"normal"}],"P70":[{"mainsnak":{"snaktype":"value","property":"P70","hash":"15ab4e8fbdbe350c4886404961abcc7350018498","datavalue":{"value":"https://www.findstat.org/StatisticsDatabase/St001963/","type":"string"},"datatype":"url"},"type":"statement","id":"Q7276290$11D73BC1-5585-4AFC-8558-681EF2D733D9","rank":"normal"}],"P1994":[{"mainsnak":{"snaktype":"value","property":"P1994","hash":"f4b0d84e0384a36adb7cb3cf1897f08320ca6c40","datavalue":{"value":"tree depth","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7276290$270495E7-23C9-488C-9307-33E24CA36006","rank":"normal"}]},"sitelinks":{}}}}