{"entities":{"Q2744384":{"pageid":2755123,"ns":120,"title":"Item:Q2744384","lastrevid":41960193,"modified":"2025-05-19T16:52:53Z","type":"item","id":"Q2744384","labels":{"en":{"language":"en","value":"Graph partitions. II"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1648975"}},"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":"Q2744384$A5EFB4B5-3354-4511-8C5F-000D42D945B5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7326a5c34f1ff681b040b08d7945d8d0f8858d48","datavalue":{"value":"0988.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2744384$E1470483-45C7-4119-9C8D-9BF4C5E51B38","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ae81cb2d5ebdd030824f9f4960520397481da4a","datavalue":{"value":{"entity-type":"item","numeric-id":1200278,"id":"Q1200278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2744384$98F01D7D-B4C7-49AA-98E8-217431746A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9413d2afd21ea26a09a8c08bef6b1b941297c39","datavalue":{"value":{"entity-type":"item","numeric-id":828984,"id":"Q828984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2744384$4484A6AB-13E4-4760-89A2-2915E6605926","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d25d55580aa033c3456b22cc344777f6eb808095","datavalue":{"value":{"time":"+2002-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2744384$EC8BE08A-62EC-4FC0-8DC2-29EC59A9524F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2744384$815F9DC9-CE07-4E45-9EEC-FBD576D9DB1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2744384$D3265E68-0BF8-4413-A573-5C4C2FF02B7A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"800dff4a81fff8f2e6ca481e838308fc5e17a91d","datavalue":{"value":"1648975","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2744384$EF83FBBB-D093-42FD-AFED-4DEC2C8799FD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b991ed5805d6a01bb085e5b7af3030e5b6ec5168","datavalue":{"value":"judicious partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2744384$244DCE5D-B87A-4014-97ED-129F079696AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"385e815ee7366374f61789438523aa769c68dd0b","datavalue":{"value":"multiway cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q2744384$BBE48A6F-42FF-4E45-9C3A-53E9771F5C1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e397c2a8db4b11795213c713522b98fd3608e10c","datavalue":{"value":"\\(k\\)-partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2744384$0C034CC7-97A3-469A-A542-7E60292C45EB","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":"Q2744384$E2D1AA7E-CD84-47CE-9DB0-2B970F412032","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2d7cc05f873a8a4bf2d69ddda86b5c9acf69d93","datavalue":{"value":{"entity-type":"item","numeric-id":3792721,"id":"Q3792721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7c1303480e9d3972916c3ca12240f83693e61ab","datavalue":{"value":{"amount":"+0.96360815","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$F2C6E280-895E-4F82-A1FF-7C8DC44B475D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6af0f283d982c8d01cb6e6ba7d00d46f3763b563","datavalue":{"value":{"entity-type":"item","numeric-id":3064394,"id":"Q3064394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3479c5c6bf8bf66b2faf9c3f1a70566b27999e6","datavalue":{"value":{"amount":"+0.9399107","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$6F9EB6CC-CFA1-40F8-8451-C373DE4E17DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af90f00337f8ec0adc9460bcb0d02496689bca47","datavalue":{"value":{"entity-type":"item","numeric-id":4304346,"id":"Q4304346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b97534641e64cfb70879097c9cf37bfa8ffa3516","datavalue":{"value":{"amount":"+0.9371061","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$FE225814-47D9-4C05-9765-57F2B6E9CD0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04ebb25e177f842a1bbe9b2706559304cc722e4d","datavalue":{"value":{"entity-type":"item","numeric-id":3335827,"id":"Q3335827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f46e76ba1b6bc6b46f921ff9db307a56b8f1ade","datavalue":{"value":{"amount":"+0.93515635","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$E9BAE704-FC89-4E76-8BA8-2EC584726DAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a7cfeaeefbcd57061be5cbb88d7b48a866ed6cf","datavalue":{"value":{"entity-type":"item","numeric-id":3650134,"id":"Q3650134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12a088fc3559ccb533b02430848fa7b2c707fa31","datavalue":{"value":{"amount":"+0.9351563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$74691245-B28D-4E47-A9D5-3A836472925F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8d49562611109b303e1f1ee8b8892cf51041b1d","datavalue":{"value":{"entity-type":"item","numeric-id":2367442,"id":"Q2367442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b04aed125066904b96893a2d7dadb169e9e511f2","datavalue":{"value":{"amount":"+0.9285388","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$AD98B452-8E65-4E9B-B951-F166276FF427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f652ef715a48951aa84824b560d50476c1d76ba2","datavalue":{"value":{"entity-type":"item","numeric-id":5752602,"id":"Q5752602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1f796fc479096c35b21057848fb7f8350fa0dc1","datavalue":{"value":{"amount":"+0.9247515","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$603F75A6-AF52-4F1F-A261-E9F63F80449B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"338ca090c66a83f7491772f78bef9d270f15ce9a","datavalue":{"value":{"entity-type":"item","numeric-id":4722114,"id":"Q4722114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b89ec1d1fd268a4d8d9ea5456de8f4b1c5b7d883","datavalue":{"value":{"amount":"+0.9227009","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$CEEAB78F-BA92-4741-B4DB-DAA21F755E20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e9d541d65f64fe6219b894b41e404f92074612d","datavalue":{"value":{"entity-type":"item","numeric-id":3801594,"id":"Q3801594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"121c4abcac2b2f739e783829e067d01d118ee6f6","datavalue":{"value":{"amount":"+0.9226117","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$1209CF80-AE8E-41F7-8A83-AD77FAB2818C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b4a832d8829c27acd2d56df6f81c675fb8d928f","datavalue":{"value":{"entity-type":"item","numeric-id":3222889,"id":"Q3222889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"268746134411a31bb2fb8c848726f0c09aebebc8","datavalue":{"value":{"amount":"+0.9211873","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2744384$96DE0551-E3BE-4971-9FCF-AEED630A224B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8110dbf5c30d58331f7a231a88f8580252636039","datavalue":{"value":{"text":"Graph partitions. II","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2744384$694E0EDA-47C1-4433-B1A6-78781016ABD8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0b959db617f3356e1c1271425a63cf65fe67e897","datavalue":{"value":{"entity-type":"item","numeric-id":6558930,"id":"Q6558930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2744384$61753BBE-EBFC-463B-BC82-1026916BBC25","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"41e5a4b37ed1b2e3106b6592b8b47b7aedc73933","datavalue":{"value":"[For Part I see \\textit{T. D. Porter}, J. Comb. Math. Comb. Comput. 15, 111-118 (1994; Zbl 0806.05032).]NEWLINENEWLINENEWLINEFor a graph \\(G\\), let \\(e(U_i)\\) denote the number of edges of the induced subgraph \\(G[U_i]\\). Let \\(\\gamma_k(G)\\) denote the minimum of \\(\\max^k_{i=1}e (U_i)\\), where \\(U_1,U_2, \\dots,U_k\\) is a \\(k\\)-partition of the vertex set of \\(G\\), and the minimum is taken for all \\(k\\)-partitions of the vertex set. It is shown that for graphs with \\(m\\) edges \\(\\gamma_2 (G)\\leq {m\\over 4}+\\sqrt{{m\\over 18}}\\); and if \\(k\\) is a power of 2, then \\(\\gamma_k (G)\\leq {m\\over k^2}+ 1.3081{\\sqrt m\\over k}\\). See \\textit{B. Bollob\u00e1s} and \\textit{A. D. Scott} [Combinatorica 19, No. 4, 473-486 (1999; Zbl 0985.05028)] for a better (in a sense, optimal) bound on \\(\\gamma_2(G)\\) and related results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2744384$2633AB2B-E9C0-42E1-8895-40C729B71005","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"706e08216f8d7e32a9bfdcc84aeeba4ad0f22d8d","datavalue":{"value":{"entity-type":"item","numeric-id":169304,"id":"Q169304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2744384$1F87232B-7B9A-4E32-8DAF-1635EC223344","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2744384","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2744384"}}}}}