{"entities":{"Q1306423":{"pageid":1317173,"ns":120,"title":"Item:Q1306423","lastrevid":46843782,"modified":"2025-12-25T17:14:05Z","type":"item","id":"Q1306423","labels":{"en":{"language":"en","value":"Highly connected sets and the excluded grid theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1347237"}},"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":"Q1306423$BAC48786-02AB-4A05-97DF-B521A925BA08","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c0564db6dbe7893782d00ab923ca4618a1cc1a1f","datavalue":{"value":{"text":"Highly connected sets and the excluded grid theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1306423$C1EA0290-2588-4A38-AA2B-A752169543E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2212e8a9d2cd66a967f22c316f8f3b61307616a8","datavalue":{"value":"0949.05075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306423$19FB3AC2-27CA-4A81-AC76-C5CA24EF3C4C","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":"Q1306423$63AB5352-F71C-456F-9761-5EA33A2DC08E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93409a5d4c83acad8ef7f368187a086954481833","datavalue":{"value":{"entity-type":"item","numeric-id":518114,"id":"Q518114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$90B64D50-581E-498E-9B25-D603861E6750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"09dde04e6ea2b126371761c3e3816489e86109de","datavalue":{"value":{"entity-type":"item","numeric-id":1306422,"id":"Q1306422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$207680BF-56B8-4811-AAD9-8F4CABC12D73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aec857263cee52fe850f36c12f5157e5c8f0a013","datavalue":{"value":{"entity-type":"item","numeric-id":228790,"id":"Q228790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$4AE31965-D3A5-40B7-B9E8-5F07E8BA44B1","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":"Q1306423$D225AD9C-11F1-43BB-9657-2C37DD541210","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eacd2e3d947d1706227d737946fa10c2f7b5f8eb","datavalue":{"value":{"time":"+2000-11-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1306423$526EAD2F-D1CB-4C2F-90A7-8B7EDB071E61","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d6e658740967aa00fa467c8319a4ee6b840604a4","datavalue":{"value":"In their work on graph minors, Robertson and Seymour prove that the class of graphs without a fixed minor \\(X\\) has bounded tree-width if and only if \\(X\\) is planar. This is quickly seen to be equivalent to the result that for every \\(r\\) there is a \\(k\\) such that every graph of tree-width at least \\(k\\) has an \\(r \\times r\\) grid minor. The authors give a new short proof of this excluded grid theorem.    The authors also propose a simple obstruction to small tree-width. A set \\(X\\) of at least \\(k\\) vertices is \\(k\\)-connected in a graph \\(G\\) if every pair of subsets of \\(X\\) of size \\(j \\leq k\\) are joined by \\(j\\) disjoint paths. The authors show that a graph has small tree-width if and only if it has no large highly connected sets of vertices.    This work is a nice contribution to the growing literature on graph minors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306423$E8C14A17-5DF6-4343-8151-0A149FE2E227","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306423$8B670B56-C134-444F-81B2-DC2EFD555BDA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a033972c20ff8e478659ac61cb96e849b01cbc4","datavalue":{"value":"1347237","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306423$5853EF2B-1DA1-4DBE-9541-4F66C539B36E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b4a7e94f67b1256fa87c9c444c77ea9a3d63a5","datavalue":{"value":"graph minors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306423$6288E59A-4472-417A-BFFC-395D592748B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c21b0233cbeaf9c19290ae71eed7a59db27ff39c","datavalue":{"value":"excluded grid theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306423$8EE5F716-4B60-4B08-931D-191EAFCBA381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306423$D3978611-8CCC-4C27-8E35-4B76A4247C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfe3638ea95b182e2e24477256f4d702d81c1ebf","datavalue":{"value":"connected sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306423$95EFA65F-3147-41B6-8350-907D4C25709F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$307FBC6E-AF9E-4EE2-8D8F-79E8AA719465","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":"Q1306423$0912C67B-EA7C-4A33-A305-2CAE59582446","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3a59f162aa470d9a693c2495834a1afa38d715f9","datavalue":{"value":"https://doi.org/10.1006/jctb.1998.1862","type":"string"},"datatype":"url"},"type":"statement","id":"Q1306423$97E57C24-3E3C-41FD-AABC-3A4B5A10A751","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5c02f8ea1d298589b400929517f477a1ef458eba","datavalue":{"value":"W2165303918","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306423$7DF32B07-2923-4DB1-AE6F-F17D98A30279","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"59f80f6e19275125de4f8e2f83f2df184481d4ef","datavalue":{"value":{"entity-type":"item","numeric-id":4342632,"id":"Q4342632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$8CFD98CE-0387-4E2A-8ACC-F7821FD2E9C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abe7b7e442ad6a82ecdca628d93eabdf846cef1d","datavalue":{"value":{"entity-type":"item","numeric-id":1275011,"id":"Q1275011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$C45B6065-EE2F-4C6E-A1F8-C97963DA604D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"906c25476b3e0b9171b3bcd342ee2ffed9189af7","datavalue":{"value":{"entity-type":"item","numeric-id":4352948,"id":"Q4352948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$BBEE75CA-7BD9-4928-8AE9-3110A023D504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30094b5b98bfe98f2cd2b8d0df9f32749353fead","datavalue":{"value":{"entity-type":"item","numeric-id":2639869,"id":"Q2639869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$454D4EFC-83FD-4996-9F35-A3DC348C41FA","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":"Q1306423$75A3CF67-B4EE-4B88-BFD2-B7AF5253F6FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e62926166610e171255ba7600cdacbb982331e7","datavalue":{"value":{"entity-type":"item","numeric-id":1179473,"id":"Q1179473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$957B901A-91E5-4BEE-A08B-FC06186D05FB","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":"Q1306423$BD4F7D24-1257-43C5-920A-566802AFFFAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e6c44e3201b3a107f5a523ae58e6a962d5f284d","datavalue":{"value":{"entity-type":"item","numeric-id":1362099,"id":"Q1362099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$4F8B329F-CD28-4E01-A986-4F6066755BBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb9436804774d1a86b2791d6813bf035d20dbdd9","datavalue":{"value":{"entity-type":"item","numeric-id":4871753,"id":"Q4871753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306423$9C7509C2-3F2A-4523-809E-5473112D26E4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1bf23ac5382d06de17e54977202a82337b925194","datavalue":{"value":"10.1006/JCTB.1998.1862","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306423$74CEEDE9-4BD7-4B17-A155-262066ECB5E7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"504772fe989a35ea27eee467a051dee6385186c7","datavalue":{"value":{"entity-type":"item","numeric-id":2941560,"id":"Q2941560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"847773b603c6b73a0e1833600f9271cae959d75a","datavalue":{"value":{"amount":"+0.8366228342056274","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":"Q1306423$7BDA7F37-8A83-45A9-81CE-0B9D8D064327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dc764b9f1a5f0baef64fa46bfe2620f5f33717c","datavalue":{"value":{"entity-type":"item","numeric-id":1850628,"id":"Q1850628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75cfaef099b28bc82e4e5dea92cd3e26970210f3","datavalue":{"value":{"amount":"+0.8187037706375122","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":"Q1306423$9A52F2C8-3455-4784-B6A1-85FE1CBE6E89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd0558ea7ec61fec5d08153e189af9218240d290","datavalue":{"value":{"entity-type":"item","numeric-id":1931397,"id":"Q1931397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"506fd53c820252d8311ed88d739369dd534e2f1c","datavalue":{"value":{"amount":"+0.8184030652046204","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":"Q1306423$E0C5EBC6-2542-4FE9-9CA9-FFFF58B60D87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7bcd639b6b18b80f06e1099442592363ce6a933","datavalue":{"value":{"entity-type":"item","numeric-id":1338321,"id":"Q1338321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0ab80beb31b4761ba6d11b658cb8d18ed5cfd33","datavalue":{"value":{"amount":"+0.8171336650848389","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":"Q1306423$43C5D5CE-DC7F-4304-9F07-4A75F135D34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e67392250539d3e3a6d01a2bb7c134e3aea2086","datavalue":{"value":{"entity-type":"item","numeric-id":3656223,"id":"Q3656223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ad6fc7a802e75a18529fd3d2fa1a655d728b17e","datavalue":{"value":{"amount":"+0.8167865872383118","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":"Q1306423$52CDE716-DBC3-4221-899E-9A9C32438E7E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1306423","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1306423"}}}}}