{"entities":{"Q1910567":{"pageid":1921309,"ns":120,"title":"Item:Q1910567","lastrevid":71137881,"modified":"2026-04-13T19:44:06Z","type":"item","id":"Q1910567","labels":{"en":{"language":"en","value":"On tree-partitions of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 858100"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$5D6C9822-6E1A-4D10-AFAB-A5437096A28E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bec379d73ebd3465152fe7d4b7e499c5415204cc","datavalue":{"value":{"text":"On tree-partitions of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1910567$DE1FA803-7F8B-48B5-8904-875FB11DEE7E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cd7c007f548192ea5d604b4f39344022202a43d7","datavalue":{"value":"0844.05078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910567$C692EC29-433D-4719-94DE-C5CF8A90B0AC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1714f8dfbde7073691ca0c8ad1a65d2295c3d8fa","datavalue":{"value":"10.1016/0012-365X(94)00337-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910567$B5C042B5-B9CE-468A-9783-3FBB769B23A2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84b3ed84bea0d94201a16bb2ea3c8899c4642452","datavalue":{"value":{"entity-type":"item","numeric-id":281609,"id":"Q281609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$8985F65E-B655-452E-8C4A-0149EC255F50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d65d4129ca311c9a2c3b258f0edfc6f2aa5c5cb3","datavalue":{"value":{"entity-type":"item","numeric-id":631644,"id":"Q631644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$1DDE4F53-C8D1-4E37-9DB9-6D3281DFC911","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$BF9C9636-B07E-4C87-83A4-6523AE94FD7F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"94a9212dfee404fb85e987f5d9b2e3c6e288c670","datavalue":{"value":{"time":"+1996-03-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1910567$36EC10E5-A8A0-427D-818A-DBE8DA001AD8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f65b0793c21403a337d86f6496251ebc59e4a57d","datavalue":{"value":"A graph \\(G\\) admits a tree-partition of width \\(k\\) if its vertex set can be partitioned into sets of size at most \\(k\\) so that the graph obtained by identifying the vertices in each set of the partition, and then deleting loops and parallel edges, is a forest. If no such \\(k\\) exist, the width is set to be infinite. The main result of the paper provides that a graph \\(G\\) does not admit a tree-partition of small width iff \\(G\\) contains a subgraph isomorphic to a subdivision of a large member from any of the four specified (infinite) families of finite graphs. Similar result concerning characterization of graphs, which admit a tree-partition such that each set of the partition is finite, was obtained by Halin. It is also formulated in the terms of exclusion of three infinite specific graphs. However, as the authors show, just excluding finite versions of Halin's graphs is necessary but not sufficient for bounding the tree-partition width.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910567$F8BA0E11-68CE-43AB-9577-F7DFC9FB7E25","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f12e1eb1be75d4426df498c29926dc868c2e1814","datavalue":{"value":{"entity-type":"item","numeric-id":187114,"id":"Q187114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$AD824A15-E9DD-4FF5-9A14-4B20E43DAB2F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910567$12DE0506-BD5B-42FC-8460-40F022FFAD13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910567$48FE772F-5A5E-4DD3-96B3-F209F7C850BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910567$775F91C2-D989-4F0D-B5BA-0AFBFD896CFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910567$A6592712-D61C-48DF-A599-384214CC1992","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"89af0fe9504f0054b44118c875d7b3f11f3aaa28","datavalue":{"value":"858100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910567$68738384-01EE-4FE7-82DB-15A748194181","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32478fd2aed385faa1920f6050cdb2b21b21c991","datavalue":{"value":"infinite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910567$320DAE0F-5DDB-4780-A76E-4F5B54CB11BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b4a7e94f67b1256fa87c9c444c77ea9a3d63a5","datavalue":{"value":"graph minors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910567$7C9DCDB7-553C-4884-91C8-EF1A2F00F3C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9abe2c7b68fa1055da3535a098ad2fc77d777e6c","datavalue":{"value":"tree-partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910567$70640D13-5536-4557-8F47-D831843E449C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccdf98bea6de3dcf3a7edd1fca9d3b62359e75d8","datavalue":{"value":"width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910567$9540A4D6-BBEF-4617-B1D0-B1CA3C2E422B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc79eafc1d9ceb1ab79797a36449e9df369395df","datavalue":{"value":"forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910567$56E9ED94-B895-4741-BC44-D848EA715311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910567$9E036F8D-4E4F-4C87-9BB0-85DA2692E854","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$57C5D6CC-F5F4-478A-9378-12718E220542","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bd21ca3716b04de4a259a4942f13a54e9e1da6b","datavalue":{"value":{"entity-type":"item","numeric-id":4857448,"id":"Q4857448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$3E017237-2AEC-481B-B4D5-8DE01A630075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e4de46336d0d07bf6a6ce03ddc464bfd06c1c01","datavalue":{"value":{"entity-type":"item","numeric-id":1183985,"id":"Q1183985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$2CBD6258-E694-44CF-83E1-6D587FA55843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b3ba00c9f098ebcdc1cd38a5931d5e60965ca09","datavalue":{"value":{"entity-type":"item","numeric-id":1121910,"id":"Q1121910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$E94C5202-0423-4B5C-B9E6-5FB7477ABEB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ef0f89b3d4848285d16b9f024f89d4a5e76a218","datavalue":{"value":{"entity-type":"item","numeric-id":799684,"id":"Q799684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$BB3E95E7-6CD4-4DD7-BCC9-95C70050BE69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0f6dd793166a567719b2fb5d958eb883aea03d","datavalue":{"value":{"entity-type":"item","numeric-id":1079583,"id":"Q1079583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$39D65FCD-2EA1-473B-91FC-4338B7927669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a583b336166cebbddf1ca439ee3458ed6982ce7","datavalue":{"value":{"entity-type":"item","numeric-id":1338321,"id":"Q1338321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$746DBF8A-59B6-4865-B439-48350580BCE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8466e8a6030720c56a95c18502dfb44c526f99","datavalue":{"value":{"entity-type":"item","numeric-id":3692864,"id":"Q3692864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910567$7BD3168F-01E1-4459-B5DA-0EDA953EB6A2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfa38122c789916807b00273af6628f4a409cae9","datavalue":{"value":{"entity-type":"item","numeric-id":1024321,"id":"Q1024321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b9873f18e44c4e9feaaae16dc062876900cef66","datavalue":{"value":{"amount":"+0.8171538710594177","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910567$B4C09657-4F3A-42DC-8766-B6359CEA069C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f81c4c79d835c00e8c4472e1874e87441c17d9f","datavalue":{"value":{"entity-type":"item","numeric-id":1307308,"id":"Q1307308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1902b272490e444786bfa94dd536581caab11ca2","datavalue":{"value":{"amount":"+0.8107163310050964","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910567$37A327DF-2356-4C99-AD78-E4DF82405418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c77a38cb520f0fe92d26ea2fc605e196d7f0532e","datavalue":{"value":{"entity-type":"item","numeric-id":4018433,"id":"Q4018433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e8661b29dd1d70bab9332578102a6dbe1aa3321","datavalue":{"value":{"amount":"+0.759334146976471","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910567$11675C84-EEF8-43CC-A5F0-FBA728075DE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6650b6ceb6b563ed25dc9fae2a0b38931089eb81","datavalue":{"value":{"entity-type":"item","numeric-id":1193564,"id":"Q1193564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf9015333aa32b980c89279b61c8a9651f8cb308","datavalue":{"value":{"amount":"+0.7525494694709778","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910567$443CF264-ECBE-41D1-ADEB-2875054FC332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca67f7d8ff80f5d4752ec6a273751d659840a560","datavalue":{"value":{"entity-type":"item","numeric-id":5902522,"id":"Q5902522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d001bc2d1ecbd13c9626318f2ef5172fca42825c","datavalue":{"value":{"amount":"+0.7515620589256287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910567$26A3646C-4BB0-47A8-910F-7845D51242BC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On tree-partitions of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_tree-partitions_of_graphs"}}}}}