{"entities":{"Q849636":{"pageid":851484,"ns":120,"title":"Item:Q849636","lastrevid":64812162,"modified":"2026-04-11T22:23:39Z","type":"item","id":"Q849636","labels":{"en":{"language":"en","value":"Upper bounds on the bisection width of 3- and 4-regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5069051"}},"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":"Q849636$B4479EC2-59C3-4A81-AD19-E83C49486400","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b895c8e94ad7577f0747f62f66531d0da826b03e","datavalue":{"value":{"text":"Upper bounds on the bisection width of 3- and 4-regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q849636$C642318B-68EF-40EE-9516-F42B1A39626C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5a63cc16e2fe60b8b06253b36e3c76811c6b0956","datavalue":{"value":"1103.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849636$DB7B8F6D-1DDF-4B14-8290-0F1D8E82E7B6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86c3523e3b1c7a7f4ded003497c81ad67b1d7c67","datavalue":{"value":{"entity-type":"item","numeric-id":718061,"id":"Q718061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$30FFB729-F653-4D54-936E-37DB086DD455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b9f391e6322208fe1ff9282b50ef9e948c0574c","datavalue":{"value":{"entity-type":"item","numeric-id":284584,"id":"Q284584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$5536378E-3739-4407-AB3C-62AE58EBCBCC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0a33251796f18919242eb286ef1f888e5d6e79da","datavalue":{"value":{"entity-type":"item","numeric-id":350720,"id":"Q350720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$438E74F5-DDEB-45C7-BA4A-9A9476C1C08B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e652df40e88a7517140c29fd3339f7b3a9de3e3d","datavalue":{"value":{"time":"+2006-10-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q849636$4BA18356-7564-4708-A163-C24993951E11","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2935a4d72202fb1449da433a358e9aac9acc7246","datavalue":{"value":"New upper bounds are obtained for the bisection width of graphs that have a regular vertex degree. It is shown that the bisection width of sufficiently large 3-regular graphs with \\(| V| \\) vertices is at most \\(( \\frac{1}{6}+\\varepsilon) | V| \\), with \\(\\varepsilon >0\\). For the bisection width of sufficiently large 4-regular graphs it is shown that \\((\\frac{2}{5}+\\varepsilon) | V| \\) is an upper bound, with \\(\\varepsilon >0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q849636$D84FE7F7-7226-4DD0-B9E0-9D5898AFB4A6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c82436212510eb3fd57a05c9debac7e41dff5f00","datavalue":{"value":{"entity-type":"item","numeric-id":226578,"id":"Q226578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$C17AC467-B630-4C7B-81F4-0AC29CB4B19C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849636$479F2DFF-CE63-4A6E-A036-D488017A1695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849636$EAEAF3D3-5204-46BD-A06C-26E32A11D85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849636$EDA84456-5E92-4E0B-BB2C-3A4B0B690C7B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d3a49db1b6b12d5cbb791d96c1e5a5ace93f8f0","datavalue":{"value":"5069051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849636$E3818C61-E68D-407B-A774-98E3B620146C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e242af08a265f147fecdde71acc893f1df2b816","datavalue":{"value":"graph partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q849636$EB52D154-1D7F-4E64-9A61-432B98B3ED2D","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"a65b384ffe1c960294b7ce2081abf2bd6d6f2943","datavalue":{"value":{"entity-type":"item","numeric-id":16276,"id":"Q16276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$38C39786-D815-402E-B73F-FD35E2E702FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"f25700f85175bfd096aca4d7332c294bf665e40f","datavalue":{"value":{"entity-type":"item","numeric-id":32336,"id":"Q32336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$483BF4D7-B61D-479E-9998-D3218C23DE89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"b4af7ae296d1737060749e5a6ebce38024334944","datavalue":{"value":{"entity-type":"item","numeric-id":19834,"id":"Q19834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$C8816081-ED07-4BEA-9CDD-816FC1554EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"f057eb724e3cb6d4a319b02c78d7523657f92461","datavalue":{"value":{"entity-type":"item","numeric-id":17132,"id":"Q17132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$33342AC4-B546-400B-B80A-8A5CFF4E18AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"3bfe7113991c4c28e9bdd52c1758350b235dc082","datavalue":{"value":{"entity-type":"item","numeric-id":21619,"id":"Q21619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$BAEBF105-0008-4823-AC82-EB404B7E39AD","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":"Q849636$C2EC0B15-95B1-421E-A328-C180F6681D35","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"167f0d0564ad0851a12caa01bbb579479de267f0","datavalue":{"value":"https://doi.org/10.1016/j.jda.2005.12.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q849636$2D4579CF-6C3B-419B-9752-97FD7F2F421F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b8e141f11ebc35c9352de7ac19d533ef71d3150e","datavalue":{"value":"W2055190409","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849636$E906904C-5F4A-4D93-B806-2B6734E5546C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0ac931768cf5405515bfb7d00781064cc5d4552","datavalue":{"value":{"entity-type":"item","numeric-id":4348783,"id":"Q4348783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$71B78186-2A58-413C-8F66-FB26436D13E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02d6721a51ab0df2abbb492d03aca241c5a1d2b7","datavalue":{"value":{"entity-type":"item","numeric-id":2766666,"id":"Q2766666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$E39B0E67-C7A0-4267-BF9B-BEF9ACCD68E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"605a729f1f85d157447c75fa885e8d9214393760","datavalue":{"value":{"entity-type":"item","numeric-id":1348690,"id":"Q1348690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$47F806C4-8244-4EB0-B56C-FEB1123D3101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de613908d2cd012d4fcbd4fd9626fc061166750c","datavalue":{"value":{"entity-type":"item","numeric-id":1120601,"id":"Q1120601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$FDEB785F-BE95-48FF-A6C1-965458E8695E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"310c4410e762a3e348723e6e57f6dee9ba9d8f75","datavalue":{"value":{"entity-type":"item","numeric-id":4729817,"id":"Q4729817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$D361666C-C2FA-4512-AE87-A4AADDFE9B8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cebe1ac89cbad0a18033276313352b27e9ca82d3","datavalue":{"value":{"entity-type":"item","numeric-id":1200273,"id":"Q1200273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$B913B8BA-83A3-4611-948A-9DD57E624928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66b4448978f1def626c75ba4509c3ccd05dbf27c","datavalue":{"value":{"entity-type":"item","numeric-id":4859012,"id":"Q4859012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$51CE47AF-E34E-4E89-B16D-8A9CBF51CC0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61807b8a1aef4284dae2ccdada18b845d5cfbdbc","datavalue":{"value":{"entity-type":"item","numeric-id":3877805,"id":"Q3877805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$0F5B3871-DD71-4778-803B-C4B70BEE14B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1091281e7a9772f75b8801ec0d3c33455090e16e","datavalue":{"value":{"entity-type":"item","numeric-id":2784494,"id":"Q2784494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$978A9A69-7C29-4843-9D6B-8D5E473C75ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$129EDA38-B41B-434A-BF1B-1B37D7925772","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d183c7288c0b0d350a148c629adf82e7b439c3d","datavalue":{"value":{"entity-type":"item","numeric-id":5286666,"id":"Q5286666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$2F10A09D-FD63-478B-92A8-977F8443C44F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b9a315bc857914b22e6f23c0d8a62ad384132df","datavalue":{"value":{"entity-type":"item","numeric-id":4027167,"id":"Q4027167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$0BA02F16-05BD-485D-9BC8-D5352DE6DEFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77ab4c5541b65bb9684e60c8818fa0ef119f1d23","datavalue":{"value":{"entity-type":"item","numeric-id":4321509,"id":"Q4321509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$B5AD94E2-524D-4808-B3A4-A3700E8C9BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10ccf4d42c4757827ddea695c7555934bd0854b7","datavalue":{"value":{"entity-type":"item","numeric-id":1112836,"id":"Q1112836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$0D117956-F7F5-40CF-8F3D-6223501D7CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1ed2ce67075a87cdb4040d4b3440a4f78bd3b15","datavalue":{"value":{"entity-type":"item","numeric-id":920104,"id":"Q920104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$59F25251-9B80-43BB-8CD6-FCC4D2E000E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ab1bb3fea25d37273520a93b75d353b55f5193c","datavalue":{"value":{"entity-type":"item","numeric-id":1333324,"id":"Q1333324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$4FBD89F2-7697-432B-ACA4-5651B498CAF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"657253338d628e8453f4374950535a5deecd10c0","datavalue":{"value":{"entity-type":"item","numeric-id":4779170,"id":"Q4779170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$F52A8C19-9B46-4CC1-8F21-6276C6106109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5207b2e2e6fa3bbd01b48889f1444981c7d441bb","datavalue":{"value":{"entity-type":"item","numeric-id":1583343,"id":"Q1583343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$EBB22136-0157-4406-BFDF-EB73D3FEAFD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe73e3265d62424d448cf8641ce587dab7d046ce","datavalue":{"value":{"entity-type":"item","numeric-id":4409104,"id":"Q4409104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849636$218DE783-4363-4C10-B159-002C5F4133BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"063ff25eb861858b91563e976cc79a2a8a1610ce","datavalue":{"value":"10.1016/J.JDA.2005.12.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849636$4341782E-1D4F-4E99-80BE-71ED14F07B1C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e78ddd39dc687f4b6a3fa261dc49417de6c9d9c9","datavalue":{"value":{"entity-type":"item","numeric-id":4779170,"id":"Q4779170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d008db5a8963936a12a01aa42074e044a1aefb6","datavalue":{"value":{"amount":"+0.9930497407913208","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":"Q849636$03957E31-BF99-45B2-A3E1-7C3C01F6DB35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7119cdc7e50d1212ea7007d23247f530e62c8246","datavalue":{"value":{"entity-type":"item","numeric-id":2766666,"id":"Q2766666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f65f53ab80bb305a4b48ac111473ab4e14684a6d","datavalue":{"value":{"amount":"+0.9919220805168152","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":"Q849636$1C0A94CF-2D4F-466D-8F04-7E0D80384990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1dfe8556581e9fd4777be51d01c34a6e417f6e0","datavalue":{"value":{"entity-type":"item","numeric-id":2381523,"id":"Q2381523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cebbf3bae39d8f6dcf2ec43eab7ab08ee781b2e","datavalue":{"value":{"amount":"+0.8576356172561646","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":"Q849636$05EBD15F-0A21-4FA2-B525-B4D44D4EDFD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55f88a4025e4a8b3afb10a2359fe27be808610ac","datavalue":{"value":{"entity-type":"item","numeric-id":6106297,"id":"Q6106297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ede69501a4e3547fc699eedf98109ff9ea602419","datavalue":{"value":{"amount":"+0.8573808670043945","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":"Q849636$CEDC701C-88CD-447E-937A-B9247438B0BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d515a16e9960bd3d0ae2d714d1aaf752265db1dc","datavalue":{"value":{"entity-type":"item","numeric-id":4729817,"id":"Q4729817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69638d5831c5d06307c93b2907f2d0fd132c1103","datavalue":{"value":{"amount":"+0.8498401641845703","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":"Q849636$EB8F647C-9135-472E-97A9-48AC57AA7A1C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Upper bounds on the bisection width of 3- and 4-regular graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Upper_bounds_on_the_bisection_width_of_3-_and_4-regular_graphs"}}}}}