{"entities":{"Q1193564":{"pageid":1204313,"ns":120,"title":"Item:Q1193564","lastrevid":66455379,"modified":"2026-04-12T10:11:21Z","type":"item","id":"Q1193564","labels":{"en":{"language":"en","value":"The structure of \\(TK_ a\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 64852"}},"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":"Q1193564$EAA0B5D8-C139-4B23-A10F-555ACADE3A0E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f7faf9ffa3edb05677f422e5966040874702b873","datavalue":{"value":{"text":"The structure of \\(TK_ a\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1193564$C14FB8DD-C861-48F1-B464-2640D6178AB8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ec876bde1d8e17f1bcd62a6e0518c3dd4d9d3d6b","datavalue":{"value":"0764.05078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193564$B7EAB8C1-ED35-4B05-A844-09BA774D43BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b93a1d3fbc2a77fb0cd80be52350d2aba473d37b","datavalue":{"value":"10.1016/0095-8956(92)90054-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193564$B74BCAA0-7467-40CA-A90B-89FB34F98E97","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193564$09F9C46B-8507-499E-B5E7-B6C847C4A5DD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1193564$B503DDAF-3F58-4E78-9E25-4722278323F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f99c38cfb2aecc529759d788d8dfe4796180bfab","datavalue":{"value":"A well-known theorem of Halin implies that the graphs not containing a \\(TK_ a\\), where \\(a\\) is any regular uncountable cardinal, can be decomposed into induced subgraphs of order \\(<a\\) which are arranged in a tree-like fashion. This observation is formalized by the new concept of a generalized tree-decomposition, which is shown to extend in a natural way the familiar tree-decomposition of finite graphs. If is proved that the \\(TK_ a\\)-free graphs can be characterized purely in terms of these decompositions: a graph is \\(TK_ a\\)-free if and only if it admits a generalized tree-decomposition into subgraphs of order \\(<a\\) such that every branch of the corresponding decomposition tree has length \\(<a\\). This result was obtained concurrently and independently by N. Robertson, P. D. Seymour and R. Thomas, who also extended it to singular \\(a\\) and to \\(a=\\aleph_ 0\\). This latter characterization has in turn been refined by the author, in a recent note which describes the structure of the \\(TK_{aleph_ 0}\\)-free graphs in terms of their normal spanning trees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193564$12BE1F8B-76A5-4890-A0BC-BFF661741084","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193564$6DAE650D-02B4-4E43-9294-EB3A183A077C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a9e610daeaa668c524e73d5c8e6e3e72fdb502c6","datavalue":{"value":"64852","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193564$24A00F43-6984-4D64-B53D-9C721EBB4DA0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8af9b0cf17829cdd2a78e30f9180c9f9b71ed888","datavalue":{"value":"\\(TK_ a\\)-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193564$F09E0EBA-B851-4554-935D-561C15D311C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a0073252dacd10c817f83ebbc24da5c2405f50f","datavalue":{"value":"tree-decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193564$91FF2F10-B98F-4525-BCC0-92FE2E9096F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193564$78FDD8B6-5BEA-4DDB-92D0-756CBA7D2D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6144280334559a6115bb843e62e7394a2e844ae4","datavalue":{"value":"structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193564$0E73F523-1E8F-449E-99E7-61DD30FDBFAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a2a0061134b0d57b6a065d5612a54533f99ed40","datavalue":{"value":"normal spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193564$85B446CB-8BD7-40DE-B841-2B8E67937165","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"494e2890710dc5d5dbbdf888620eb758b4d58ddf","datavalue":{"value":{"entity-type":"item","numeric-id":215083,"id":"Q215083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193564$7C1A891A-0EDA-4E15-975D-445B925C1BFA","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":"Q1193564$B24754CB-30DD-49A4-8C6A-8971C26F3063","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c7fde4db9bec80dc2ae3921bc02d4e3eda81b1b8","datavalue":{"value":"https://doi.org/10.1016/0095-8956(92)90054-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1193564$96263D25-4A23-4F61-A215-CF6CEEB8B47C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"476970253eb33f752effec01651dc895c7e6c494","datavalue":{"value":"W204002426","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193564$9E301A5A-9ADE-47C3-9FC7-07A404B562B7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"feeda177033aefb91b710e1d67c7f3f979071c88","datavalue":{"value":{"entity-type":"item","numeric-id":2641316,"id":"Q2641316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193564$8BEB89B8-F61D-45B8-8FE9-FA4CD1EC558C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27dc88e90c2a5e80ee7fe153685cd6e97e723db5","datavalue":{"value":{"entity-type":"item","numeric-id":3999150,"id":"Q3999150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193564$3E780F5E-BC41-49CC-85E4-6F6B125B991C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"234ad6262cf9e2886c9dfbbba7da18830e2c1e58","datavalue":{"value":{"entity-type":"item","numeric-id":5522046,"id":"Q5522046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193564$0849F1A4-7169-4417-A156-8FA3C249E6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddb209b5f842758c420a337fc7ccf411f373b50b","datavalue":{"value":{"entity-type":"item","numeric-id":2526108,"id":"Q2526108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193564$F4746AE2-F338-48C4-AF9E-F0BC253D3446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71dec187432dd5bb05dd74f8bf7fc17226d1194d","datavalue":{"value":{"entity-type":"item","numeric-id":4117857,"id":"Q4117857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193564$F33DA5F0-D254-40EA-8B75-7E0D28BB7236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95266b08d8764b1b42caf4401af1db66feedc701","datavalue":{"value":{"entity-type":"item","numeric-id":5558478,"id":"Q5558478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193564$80BEB094-3DCD-47F7-8B32-05B2AB3E93DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56ab210fff5d79b2e4d4ad18f1a46804c4d49944","datavalue":{"value":{"entity-type":"item","numeric-id":1410732,"id":"Q1410732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193564$7EFBF41C-A985-4AB8-A876-9CC6610588BE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a4f84d414318e7cfd1cc5edf2b918c4245e7ae6","datavalue":{"value":{"entity-type":"item","numeric-id":1333343,"id":"Q1333343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8530e4c22217f0866ac4c8d9827b8d7645e80b4","datavalue":{"value":{"amount":"+0.7945563793182373","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":"Q1193564$70B2EF9F-461F-4A6E-B248-B32171F62199","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":"b2e2c3d8626184d02da371eb2a4ff7c91a06c31b","datavalue":{"value":{"amount":"+0.7893673181533813","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":"Q1193564$A2C4F6A1-238D-454B-BFD5-A1F2D54CF34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d80a5c47717d2aee8b3852ce1977ed1b0f10971e","datavalue":{"value":{"entity-type":"item","numeric-id":1410732,"id":"Q1410732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"977cc454673bd7ec809093a1a368633f8e87c677","datavalue":{"value":{"amount":"+0.7797912955284119","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":"Q1193564$5630D27D-DEFA-46E3-AC51-50C199F4F497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0222beb2abb0c8672b24e5b0ce70dedb497f6e35","datavalue":{"value":{"entity-type":"item","numeric-id":3150978,"id":"Q3150978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"866b2e5197ac279c2cd9436203ba0f2effe8def9","datavalue":{"value":{"amount":"+0.7694857120513916","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":"Q1193564$80DF9A64-91E8-4925-A3A4-430500E631B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0161d2e57354c23fb5a6b7b7663f6d93384d90f","datavalue":{"value":{"entity-type":"item","numeric-id":3032288,"id":"Q3032288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"866b2e5197ac279c2cd9436203ba0f2effe8def9","datavalue":{"value":{"amount":"+0.7694857120513916","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":"Q1193564$2B610491-4215-4FCC-8D1A-08C5558C7357","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The structure of \\(TK a\\)-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_structure_of_%5C(TK_a%5C)-free_graphs"}}}}}