{"entities":{"Q6131741":{"pageid":13266048,"ns":120,"title":"Item:Q6131741","lastrevid":58708380,"modified":"2026-04-06T10:15:30Z","type":"item","id":"Q6131741","labels":{"en":{"language":"en","value":"Highly connected graphs have highly connected spanning bipartite subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7834202"}},"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":"Q6131741$AD51548C-04AB-4532-85FC-8DD940ED5709","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bc8f2fdc40446d06e495c09a240557a206ed88e2","datavalue":{"value":{"text":"Highly connected graphs have highly connected spanning bipartite subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6131741$D79B961F-66D4-4288-A430-71E522588693","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a46939f76ae057860543f537378c61e89da028ca","datavalue":{"value":"10.37236/12084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6131741$82E5454A-B3A8-4CEE-BBBD-50C99F2BAF99","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"58695e9da83c43913be67e6d6be310d1075b58c8","datavalue":{"value":{"entity-type":"item","numeric-id":222643,"id":"Q222643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6131741$EDD4C736-30E2-4FEF-8547-8D09293775D8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6131741$63666760-A353-47BD-A6D3-D0F36F31A610","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7cc26b4b6ce89b5f72b36d6fbe49129d9f7892b3","datavalue":{"value":{"time":"+2024-04-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6131741$A4A2FD43-DE4C-41B0-AA10-A9098A795C0D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8c1f70f446ba8fdd72658466c92a391d082be5f3","datavalue":{"value":"https://arxiv.org/abs/2403.15599","type":"string"},"datatype":"url"},"type":"statement","id":"Q6131741$DD3C8DBB-DD1A-42FB-A1A4-088207B9B1DB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2b7ffd3a724f8af4ec128dc741ad3dd925073b84","datavalue":{"value":"Summary: For integers \\(k\\), \\(n\\) with \\(1 \\leqslant k \\leqslant n/2\\), let \\(f(k,n)\\) be the smallest integer \\(t\\) such that every \\(t\\)-connected \\(n\\)-vertex graph has a spanning bipartite \\(k\\)-connected subgraph. A conjecture of \\textit{C. Thomassen} [J. Comb. Theory, Ser. B 35, 129--141 (1983; Zbl 0537.05034)] asserts that \\(f(k, n)\\) is upper bounded by some function of \\(k\\). The best upper bound for \\(f(k, n)\\) is by \\textit{M. Delcourt} and \\textit{A. Ferber} [Electron. J. Comb. 22, No. 3, Research Paper P3.2, 8 p. (2015; Zbl 1327.05133)] who proved that \\(f(k, n) \\leqslant 10^{10}k^3 \\log n\\). Here it is proved that \\(f(k, n) \\leqslant 22k^2 \\log n\\). For larger \\(k\\), stronger bounds hold. In the linear regime, it is proved that for any \\(0 < c < \\frac{1}{2}\\) and all sufficiently large \\(n\\), if \\(k=\\lfloor cn \\rfloor\\), then \\(f(k, n) \\leqslant 30\\sqrt{c}n\\leqslant 30\\sqrt{n(k+1)}\\). In the polynomial regime, it is proved that for any \\(\\frac{1}{3} \\leqslant \\alpha < 1\\) and all sufficiently large \\(n\\), if \\(k=\\lfloor n^\\alpha \\rfloor\\), then \\(f(k,n) \\leqslant 9n^{(1+\\alpha)/2}\\leqslant 9\\sqrt{n(k+1)}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6131741$6130756B-C688-4042-8477-01CFF3E21895","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6131741$A1A81A0A-54B7-4D13-9451-4A7B16D0B1FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6131741$DA0ECD11-9787-4C07-857E-31534C448026","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6f339597e1d843ff1a59040b2bf07e7ae6a0467c","datavalue":{"value":"7834202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6131741$4C8BAE48-2676-4E78-A50B-1C5174F17C90","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fcc056f08909b3ad1299ecc6285971e30b5df36","datavalue":{"value":"large girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q6131741$1DD66FC3-4116-4704-9108-47F9D0B31D6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fae8dc69695ed62681f89d7d9eea2d8a16b8684","datavalue":{"value":"minimum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q6131741$63006862-DBB2-40C9-8CF9-83BA54E03A21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b8a0b4a41e376202718b0fc34c6d1807c7bec11","datavalue":{"value":"cyclic vertex-connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6131741$900C50B5-0FCF-4DDD-B540-FB292B38BEB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fa730215979a24c4645d8813705adab3763e72c","datavalue":{"value":"disjoint cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q6131741$8BDF7826-F84E-4066-BE4B-561F27CA8D21","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":"Q6131741$0BF21479-2AC5-40F8-816E-A76E19ED4042","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef520cfff57d2b71c38e27db1adf330acc0b0e8d","datavalue":{"value":{"entity-type":"item","numeric-id":2517648,"id":"Q2517648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16ba51d170f5dc3be74a58a85ae1613ce4b2dc58","datavalue":{"value":{"amount":"+0.8462048172950745","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":"Q6131741$ED2FC540-BA7D-4DCE-9AA3-7BCE5967E622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab19b0756ba145af4abf4e73a1c63b45486d246a","datavalue":{"value":{"entity-type":"item","numeric-id":6057659,"id":"Q6057659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcee6df76effb92decc451cad0722552dae039d9","datavalue":{"value":{"amount":"+0.7879172563552856","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":"Q6131741$A33C7C8A-89CD-4F58-BA50-70635E0FBDE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b2ed06284d54b1fe6aa2834244b9f712a578205","datavalue":{"value":{"entity-type":"item","numeric-id":5463356,"id":"Q5463356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"554ae40becf778978a29a8ab3983583d43f5e7c7","datavalue":{"value":{"amount":"+0.7813931703567505","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":"Q6131741$EC9D6B66-0D27-4026-A9A1-DAC28729A7E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6764661d1cded4f465b2b5bdc03e976010f1721","datavalue":{"value":{"entity-type":"item","numeric-id":510552,"id":"Q510552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2256935e5c0ecbc5951010e9886fe3338535bd1a","datavalue":{"value":{"amount":"+0.7771284580230713","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":"Q6131741$7C55261B-097F-48D0-8D77-4A16C68BB036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db0e7124406dc9e5cababa5e42f0d73a32dbc809","datavalue":{"value":{"entity-type":"item","numeric-id":1746581,"id":"Q1746581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59a263636b6f51a6a547894341222beabb90b449","datavalue":{"value":{"amount":"+0.7766518592834473","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":"Q6131741$21C5E760-584E-4979-95CC-AD2F69A5AB9E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6131741","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6131741"}}}}}