{"entities":{"Q1405114":{"pageid":1415854,"ns":120,"title":"Item:Q1405114","lastrevid":48161395,"modified":"2026-01-03T20:06:25Z","type":"item","id":"Q1405114","labels":{"en":{"language":"en","value":"Partitioning into graphs with only small components"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1970687"}},"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":"Q1405114$34F653D3-DD17-425B-A6A5-5D9652C4BF23","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e145441b3cb56fbf216221aa433c1a9cfaecf77e","datavalue":{"value":{"text":"Partitioning into graphs with only small components","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1405114$FBC0CF09-B240-4FF7-A3D5-824943AF6043","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"80fe040f0ff8f29842db268750a9ff4a1a14402c","datavalue":{"value":"1023.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1405114$BECAB30B-D659-4B22-AED8-6C42F54A8178","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"973bcfb8174835acd8d310700e2769234fd96daa","datavalue":{"value":"10.1016/S0095-8956(02)00006-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1405114$C228B35B-5F1E-4C1A-9D60-1EE4513C7FF8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$F812AE1C-AD4C-45B9-A6EF-A8DC9CE63B6C","rank":"normal"},{"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":"Q1405114$C166A7B5-8770-46D6-B42A-4030067491E3","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":"Q1405114$DF7D1F0A-4484-4C7B-9CF9-1225ECB7AD53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00965660cfd4395683a2a338f67e7ff433027b46","datavalue":{"value":{"entity-type":"item","numeric-id":234402,"id":"Q234402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$F489877D-E268-4993-BFBE-200C07FF7711","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":"Q1405114$BF20D482-7E59-4DA8-B553-54F2F70DE7FF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"988a1f1f38c2f749de54c12ebc5774f827c2b17e","datavalue":{"value":{"time":"+2003-08-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":"Q1405114$5D124E0C-CC36-4C43-82FD-D7E488C71E1C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dca69605e74c310cac7847dc3eb018be969f0d07","datavalue":{"value":"The authors prove several results on edge partitions and vertex partitions of graphs into graphs with bounded size components. The main results are:   (1) Every graph with maximum degree at most \\(\\Delta\\) and tree-width at most \\(k\\) admits a vertex partition into two induced subgraphs \\(G_1\\), \\(G_2\\) such that each connected component of \\(G_1\\) and \\(G_2\\) has at most \\(24k\\Delta\\) vertices, and an edge partition into two subgraphs \\(H_1\\), \\(H_2\\) such that each connected component of \\(H_1\\) and \\(H_2\\) has at most \\(24k\\Delta(\\Delta+1)\\) vertices.   (2) Every graph with maximum degree \\(\\Delta\\geq 3\\) admits a vertex partition into \\(\\lfloor\\frac{\\Delta+2}{3}\\rfloor\\) induced subgraphs \\(G_i\\) such that each connected component of \\(G_i\\) has at most \\(12\\Delta^2-36\\Delta+9\\) vertices.   (3) Every graph with maximum degree \\(\\Delta\\geq 2\\) admits an edge partition into \\(\\lfloor\\frac{\\Delta+1}{2}\\rfloor\\) subgraphs \\(H_i\\) such that each connected component of \\(H_i\\) has at most \\(60\\Delta-63\\) edges.   (4) For every integer \\(n\\), there is a planar graph of maximum degree six such that in every vertex partition and every edge partition \\(\\{G_1, G_2\\}\\), one of \\(G_1\\), \\(G_2\\) must have a connected component with at least \\(n\\) vertices, and there is a planar graph such that in every vertex partition \\(\\{G_1, G_2, G_3\\}\\), one of \\(G_1\\), \\(G_2\\), \\(G_3\\) must have a connected component with at least \\(n\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405114$5645A2DF-D48C-404C-A3D4-A98A951B0ECB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$A522D4E4-E0BC-4EB7-858D-FD4C2EF86D6C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1405114$85128B38-8C76-4E34-8B4A-F80B3D984BFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1405114$217F7B9B-D6C2-45CC-A4DD-4346D2C8FA12","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"60d5bf76688cae1b8bde4985f4b5cb4b34f2c57b","datavalue":{"value":"1970687","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1405114$0CEF5CDC-A0FF-4F16-B5B5-69C0D832157B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405114$1BD6DA58-2622-4F9B-A75B-E6F5E72841E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca3a7448755b7a50ac3116645c7263a056e331af","datavalue":{"value":"vertex partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405114$C18E0A2E-87CF-4F45-9DAB-2B35AD216776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69682a3e6cff6ef8ba066a08c66766cdbf92ca1a","datavalue":{"value":"edge partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405114$5593CA13-5214-4EB5-8365-10CECB8026BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405114$39D72EE8-9134-4A82-9DFC-8F6B5AF6B30E","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":"Q1405114$ECDF055A-3A26-4940-B686-B46A14C5FF3F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e17930ace03f213f5b8645e946d5833d008a0499","datavalue":{"value":{"entity-type":"item","numeric-id":1120581,"id":"Q1120581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$8D2A620B-E55F-43A8-8FAB-EB8A04467195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$CF78874F-EF16-44F0-BD0C-59D00906A480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"135d5599cd89f5ef17047c8d4f9e048cb6f376d3","datavalue":{"value":{"entity-type":"item","numeric-id":5936088,"id":"Q5936088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$799A2E49-4E1F-4F59-83BB-714E72B3186A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdc87f88af05c1d3ed5bd6b6332d62b8ba1653c7","datavalue":{"value":{"entity-type":"item","numeric-id":1826951,"id":"Q1826951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$9DC5F396-2D42-4B7B-B7A0-6A1AEDB161F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"964d24fee59e2b000cf26fdc45697dbd34415c67","datavalue":{"value":{"entity-type":"item","numeric-id":1910567,"id":"Q1910567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$EE3E4859-7A38-4295-8968-182E21F61D0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb4cd0043520378950644a1497cfc0310df533c0","datavalue":{"value":{"entity-type":"item","numeric-id":1405114,"id":"Q1405114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$02F9F6D3-1C07-4899-AD4B-FA7B41315C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ce1b86400443e0ae20d58e94201235ac6cd7626","datavalue":{"value":{"entity-type":"item","numeric-id":5725269,"id":"Q5725269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$719E3D62-E336-43AC-96AB-221834F70AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc047fee827268807f48ff95dc135be32e1a536c","datavalue":{"value":{"entity-type":"item","numeric-id":1842168,"id":"Q1842168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$D643CAAD-2E1D-4C42-8A68-54A80CA00C3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74074974e02935f8f5ecb942cc6fe70f08b746ea","datavalue":{"value":{"entity-type":"item","numeric-id":5530470,"id":"Q5530470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$29EC0D49-06BE-40CF-AF95-F0B7825AA0F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d121cdeb1c638d1e652d84e6b13b6dcfaac9d2b3","datavalue":{"value":{"entity-type":"item","numeric-id":1306426,"id":"Q1306426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405114$AE8BBB82-B3B3-4AE4-AB58-343AC975EE65","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efe9cadba59964d7459ce4dd02181627c10693ca","datavalue":{"value":{"entity-type":"item","numeric-id":1400964,"id":"Q1400964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b2ad417a00478cc418b7280318c9aeb03cbaaec","datavalue":{"value":{"amount":"+0.8640575408935547","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":"Q1405114$DC10E5E4-B726-4DAB-B30F-0CE6CD65BD39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22fb1a2c73bd9e36ebf9a9580532f7ca7c77c46b","datavalue":{"value":{"entity-type":"item","numeric-id":4474279,"id":"Q4474279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d0de2ad92832286f37ce1145f7a3aa8692dca9c","datavalue":{"value":{"amount":"+0.818091094493866","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":"Q1405114$705021D5-DAA5-4432-9DBF-B4C05DA14154","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":"50b812f36840af53f8a8839db96a3a45573aa661","datavalue":{"value":{"amount":"+0.8168336153030396","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":"Q1405114$CC925651-9AE1-4FC3-B99B-898DC47D8AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75a99ae36229e6a244314644f12058939c2619a1","datavalue":{"value":{"entity-type":"item","numeric-id":4908827,"id":"Q4908827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41ce94682542f03204164d1853ae7be27b200b0c","datavalue":{"value":{"amount":"+0.816144585609436","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":"Q1405114$0D462D9B-8318-4214-8803-6E705AEBE10D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"722ca604c86c4f89d63941428081cd52403161a4","datavalue":{"value":{"entity-type":"item","numeric-id":2294901,"id":"Q2294901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da9527adbedd4a749dc338d0ab2e3ce127588a7f","datavalue":{"value":{"amount":"+0.8155339360237122","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":"Q1405114$07C67FE2-B77B-4450-BF6C-829A421F1F96","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1405114","badges":[]}}}}}