{"entities":{"Q2875685":{"pageid":2886405,"ns":120,"title":"Item:Q2875685","lastrevid":52061945,"modified":"2026-01-20T20:54:32Z","type":"item","id":"Q2875685","labels":{"en":{"language":"en","value":"Maximum balanced 3-partitions of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6328437"}},"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":"Q2875685$A4E74C93-F568-4702-B4C9-E41C293C9B52","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"040f6b3ad2f50a978ab4f028f96034823bdc3f6a","datavalue":{"value":"1300.05257","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875685$C073A69B-4DED-494C-A9D8-D64588F9D2CB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"01bbb3d53d47efd021914b7a46755c5b7acd7c0e","datavalue":{"value":"10.1142/S1793830914500207","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875685$6FC8E258-649C-443E-855C-DB23DFCCD343","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"70e679fee6e4f21d017c0072864e07e595407761","datavalue":{"value":{"entity-type":"item","numeric-id":2788714,"id":"Q2788714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875685$E62A9998-94BC-4A3D-B93D-51F06FC72A7E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c866af9eeba29f78c69a6ed1b459a3cf1e984e30","datavalue":{"value":{"time":"+2014-08-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2875685$5670268E-8E6F-4917-8E13-A15E9C0B312E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875685$BD7808AE-E5ED-448B-AA7C-0570577A03BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875685$E6EED2DC-0192-4E15-96C8-3F6F04562BAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875685$C9235B62-E879-4D14-BE5C-5757924192BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"36c02be602c28592819d229099534ed5e1318174","datavalue":{"value":"6328437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875685$062FF713-FB47-4829-A6DD-E02926FBAE52","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11276b72beda47825ef58b213a852b5b22c17fcd","datavalue":{"value":"balanced 3-partitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875685$694A4E6F-1695-430E-BD7E-97D35325170A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f0963e48f55d2fd3ecacf39725f5cd79bc14a99","datavalue":{"value":"judicious partitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875685$63DCC9FA-BE3C-4344-86F4-D80822B9340B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1dc38be0f754177ae883115dacda27973fe6a895","datavalue":{"value":{"entity-type":"item","numeric-id":1793466,"id":"Q1793466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875685$DDD19627-0B2C-4878-A81E-DB1F82765566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c94ab615bb0d8b6988d4216cfa31d35b807d9ccb","datavalue":{"value":{"entity-type":"item","numeric-id":593062,"id":"Q593062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875685$60201544-13B1-47E8-B7FF-2811C04A7973","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":"Q2875685$349FFACE-F3B8-498D-A7D2-67C9925EBDA0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7299c3309f1595404d86c1c96d3a1c04dcd2e81","datavalue":{"value":{"entity-type":"item","numeric-id":4708558,"id":"Q4708558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875685$D096643C-F8A8-4208-8954-7A5E8565971D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f8c1d31d8ba061827b81baef17210d84519a4d3","datavalue":{"value":{"entity-type":"item","numeric-id":2015796,"id":"Q2015796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875685$33BD38EF-3100-4845-9308-2FA8479CCAAE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa033e01cff5efc2137f1ca8dbde1519aac0a01e","datavalue":{"value":"https://doi.org/10.1142/s1793830914500207","type":"string"},"datatype":"url"},"type":"statement","id":"Q2875685$ABF0556E-0DC4-4E82-9AEF-263A310CD6EC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3ce5b52f46d90d3c0288acf37272d7b09be4d395","datavalue":{"value":"W2108613017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875685$0C845586-44F1-4CB9-BDB7-5D49083142C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b07944fae69a7a4025550f92da5b4bcd30fc8fe","datavalue":{"value":{"text":"Maximum balanced 3-partitions of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2875685$3F960846-BC72-4435-A90D-DE14986906FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3197fe9f7cff1c8c4f16e3a2367a272f1cd434a2","datavalue":{"value":"A \\(k\\)-partition of vertices of a graph is balanced if the number of vertices in two distinct terms of the \\(k\\)-partition differ in size at most 2. It is proved that if \\(G\\) is a graph with \\(m\\) edges and \\(r\\) is the maximum number of vertex disjoint paths of length 2, then \\(G\\) contains a balanced 3-partition \\(V_1, V_2, V_3\\) such that \\(e(V_1, V_2, V_3) \\geq (2m + 2r)/3\\). Actually, a slightly stronger result can be proved using additional parameters such as the number of edges in a maximal disjoint matching from the vertex disjoint paths of length 2. Also it is proved for any \\(3 \\leq p < 6\\) that there are sufficient conditions in terms of the minimum degree \\(\\delta(G)\\) and maximum degree \\(\\Delta(G)\\) such that there is a balanced 3-partition with \\(\\max \\{e(V_1), e(V_2), e(V_3)\\} \\leq m/p\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875685$7E37F5AB-877F-455F-8E61-4C5FC84ED7B5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"69ba710ec323ba2b1e2239c5bdd6e4165b935d93","datavalue":{"value":{"entity-type":"item","numeric-id":175582,"id":"Q175582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875685$5704D47C-62D2-4D28-9E33-A40E7C5D5947","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba0c5224f7fc145585e6dcfc95f872193d4a94a4","datavalue":{"value":{"entity-type":"item","numeric-id":3572701,"id":"Q3572701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"772febd5f32d16369aa13ca99c054458efb6bdc5","datavalue":{"value":{"amount":"+0.8373503684997559","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":"Q2875685$37B44AEE-8471-42A3-AD8E-A5EA046C9421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6002c1498153a2b03378a8501df94ed6d4c8f6bb","datavalue":{"value":{"entity-type":"item","numeric-id":3195864,"id":"Q3195864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34e3caf43e1a43d66a3ac7bd8d15eb0bf5dfbacc","datavalue":{"value":{"amount":"+0.8322175145149231","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":"Q2875685$998AA9C3-7F52-41A0-8F7C-BA076AD2220E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d93db7dbef17b7baeeb884c52839e3e0d0c1d3e","datavalue":{"value":{"entity-type":"item","numeric-id":709305,"id":"Q709305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cc151cc958efba87d075479739b480a56809ed2","datavalue":{"value":{"amount":"+0.8305466175079346","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":"Q2875685$D80D0C54-23AE-47AD-ABC7-E0747207C558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0ee286ad8f1fde6fef20931c61a27693aa672be","datavalue":{"value":{"entity-type":"item","numeric-id":5190331,"id":"Q5190331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"899eff9f69c12d31bf78c4d55c2aab6522895591","datavalue":{"value":{"amount":"+0.82414311170578","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":"Q2875685$85C07D32-5DEF-46F3-998B-F5A2B4CDA171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ac3ce2095e61ecc72ed2b28d24b538e4c1ad838","datavalue":{"value":{"entity-type":"item","numeric-id":3970898,"id":"Q3970898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c586e177677a52c71f449a7155053694a9d086ef","datavalue":{"value":{"amount":"+0.8240941762924194","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":"Q2875685$52737C2F-45A1-47FD-B360-E103796810C9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2875685","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2875685"}}}}}