{"entities":{"Q805628":{"pageid":807476,"ns":120,"title":"Item:Q805628","lastrevid":49513405,"modified":"2026-01-07T10:41:40Z","type":"item","id":"Q805628","labels":{"en":{"language":"en","value":"How to make a graph bipartite"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4204372"}},"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":"Q805628$8852722B-216F-41BE-ADFD-841745FD90BA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"577787b3f6247ae7d0f1a2184157a85ee8972876","datavalue":{"value":{"text":"How to make a graph bipartite","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q805628$4197B963-9D3E-4DC5-9951-DF9C6C346BB5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f3900b6ed8545445b02c9c470a0156c81edbdd6c","datavalue":{"value":"0729.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805628$9D1A870B-BFBC-4B07-BEA9-3E20E7658E77","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5b2c58851fae2edff9d3c9765ffefdba558fedef","datavalue":{"value":"10.1016/0095-8956(88)90057-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805628$CED197F3-AC33-47BE-A306-D77EF00213B3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b81a4dc49f2cef20908ab5b4ec5273f96d074360","datavalue":{"value":{"entity-type":"item","numeric-id":188717,"id":"Q188717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$E5C97529-3BAD-49F0-9D56-C8AECCF59A07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a90237f4fbe17f8aa89942b7417b8396bf1098f7","datavalue":{"value":{"entity-type":"item","numeric-id":175582,"id":"Q175582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$4DB255C4-2BE2-4331-8908-9F1729F7F2D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5614d963e1142d1d3e84430bb23fe04069b1019","datavalue":{"value":{"entity-type":"item","numeric-id":590239,"id":"Q590239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$C631631A-7698-4B8F-B266-576343D17FCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb00475fd567190194461a0f087df1793eeae7c4","datavalue":{"value":{"entity-type":"item","numeric-id":6480801,"id":"Q6480801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$BE1E0DC0-8ED4-456A-9202-976BC6F3F7AA","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":"Q805628$3A36FD35-5273-43FF-A22A-5AC2F23E15E8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q805628$E1E8A0C4-9FAA-4EDF-BD9B-0C88E9DC728B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9e8626fb57c1af33acea8495a69c2fdb60ce9efc","datavalue":{"value":"The following theorems are proved:    (1) Every triangle-free graph with n vertices and \\(m\\) edges can be made bipartite by the omission of at most \\(\\min \\{(m/2)-2m(2m^2-n^3)/[n^2(n^2-2m)],m-4m^2/n^2\\}\\) edges.    (2) There exists a constant \\(\\epsilon >0\\) such that every triangle-free graph with \\(n\\) vertices can be made bipartite by the omission of at most \\((1/18-\\epsilon +o(1))n^2\\) edges.    (3) For every forbidden graph \\(F\\) and for every \\(c>0\\) there exists a constant \\(\\epsilon =\\epsilon (F,c)>0\\) such that any \\(F\\)-free graph with \\(n\\) vertices and \\(m\\geq cn^2\\) edges can be made bipartite by the omission of at most \\(m/2-\\epsilon n^2\\) edges.    (4) If \\(f=f(n,m)\\) is the maximum integer such that every triangle-free graph with n vertices and at least \\(m\\) edges contains an induced bipartite subgraph with at least \\(f\\) edges then    (i) \\((1/2)m^{1/3}-1\\leq f(n,m)\\leq cm^{1/3}\\log^2m\\) if \\(m<n^{3/2},\\)    (ii) \\(4m^2/n^4\\leq f(n,m)\\leq c(m^3/n^4)\\log^2(n^2/m)\\) if \\(m\\geq n^{3/2}\\).    Several related questions, generalizations and unsolved problems are also considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q805628$96EFB245-D1B9-46AE-A2BE-7A573AC3E325","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805628$30288F8F-0F36-4D7E-B857-0AEFD5B29546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805628$1AAC23CE-3BDA-455F-A022-DBD9B9AB6E38","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d2e331ff2e94b702af5841fd9565f56b1fa6c32a","datavalue":{"value":"4204372","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805628$659A9AFF-E323-4FEE-98AF-1A4C199BF4CD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ce67bd27fc3ee89d8642921735100b79f0d0ab3","datavalue":{"value":"triangle-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q805628$9F85FB51-600C-4135-95CF-7B426EF511D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58d98a8e8a82d5ced11d99fa8f7f4a8fc50c0d4e","datavalue":{"value":"bipartite","type":"string"},"datatype":"string"},"type":"statement","id":"Q805628$54FDC681-5CEC-4F92-A78E-1907B3DDC790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f1c528d72117a52ae1258e9c79f4028b7c92690","datavalue":{"value":"forbidden graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q805628$84592970-FCC6-4A71-BAAA-404B86D37B80","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"030a49e2c464109236f602e1a75ee45d16e2a4dc","datavalue":{"value":{"entity-type":"item","numeric-id":588304,"id":"Q588304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$7ACF09F8-3663-4C6E-BC98-456604F4FE10","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":"Q805628$980F3676-E4E9-40D0-9CF2-89B5D3C11F9B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"44cca3f430feecf5a5f953604b27855416322d71","datavalue":{"value":"https://doi.org/10.1016/0095-8956(88)90057-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q805628$14691689-3A8E-4170-A611-C8EDA8722D6E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e0ac24450bcb79cb22bf40c2c2cd63f7fe1c48f5","datavalue":{"value":"W2989103922","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805628$1B2CFAEA-F0C1-4F99-AB15-9731638C8C8B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"81098e9793eb8e558542ea1a28a2014135afcfe4","datavalue":{"value":"Q105709587","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805628$F99CF3F3-165A-412D-8B95-EA18013D465F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d718202177874559acaa759051aa392027bdc43","datavalue":{"value":{"entity-type":"item","numeric-id":1159234,"id":"Q1159234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$FC36B79E-2D2D-44BE-97A4-E503754A1214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$EC0435B8-0C0B-4FCC-875A-788C441B6F99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$9CADD858-BA76-4E20-828E-070CA576960E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$1EA47DE9-2069-4FD2-93A6-C20ECDBEDEF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71e85ecfd1a3d32b569447215f150df8b629242d","datavalue":{"value":{"entity-type":"item","numeric-id":3277102,"id":"Q3277102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$8AFEB604-B3AC-4527-941A-02BDD65961E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f7eb309f58b39644df6e6530ed9d75edf5960d1","datavalue":{"value":{"entity-type":"item","numeric-id":3845890,"id":"Q3845890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$C4547E54-C8A1-4C73-9743-14B0B716DAF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5df05bc83b5f828f91d2699677c5b7ac22445b4","datavalue":{"value":{"entity-type":"item","numeric-id":2396159,"id":"Q2396159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$D1BAA652-AD71-40AE-B412-CDAD175A09EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c6a48c30a66c815be731bf12c0f1bd0e1b2d5ed","datavalue":{"value":{"entity-type":"item","numeric-id":4071278,"id":"Q4071278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$A000889B-F742-4D9D-AA3E-E7A8943278FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"220c5f1f35138cfaa8d4518becb9f5fbf2fff31a","datavalue":{"value":{"entity-type":"item","numeric-id":5588434,"id":"Q5588434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$A1D33E29-4A23-4F59-8BB4-C0241212E47D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ada7085ec5bf046e4252cf92ea4a3fb07dbfcfc","datavalue":{"value":{"entity-type":"item","numeric-id":5610920,"id":"Q5610920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$A6E974F4-1747-4658-976F-765A6B9A8827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44516da8b44f33725b5a5ea8f915293abb9c6743","datavalue":{"value":{"entity-type":"item","numeric-id":594896,"id":"Q594896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$E2A8E9EA-AC8D-4E29-BBC0-3607247B2C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631afda92da774b2f35528b579855e622332ed35","datavalue":{"value":{"entity-type":"item","numeric-id":4065548,"id":"Q4065548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$9625FCC8-8CC7-4F56-AF43-F7D2629EA859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca6c17b8ff50b5fec80e29bc7b20a023f3e7ea11","datavalue":{"value":{"entity-type":"item","numeric-id":3770571,"id":"Q3770571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$5212DBF1-C1B8-4185-A243-C48594137A3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42f21add934df3a015e9680036d952c5d644de27","datavalue":{"value":{"entity-type":"item","numeric-id":1245976,"id":"Q1245976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805628$B638876F-296D-402F-A569-24966DD13859","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c2718d54d9f4082b04052bab7883ff92e2b374b","datavalue":{"value":{"entity-type":"item","numeric-id":3137183,"id":"Q3137183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a85a85e9c6453add7b3dc8ee71929af03336ad4","datavalue":{"value":{"amount":"+0.8783500790596008","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":"Q805628$E0E2A753-7B28-4CC0-B0D1-63393939F850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"830c35e9b80d545fa8338c77b0c89c7819ba2734","datavalue":{"value":{"entity-type":"item","numeric-id":4866251,"id":"Q4866251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a85a85e9c6453add7b3dc8ee71929af03336ad4","datavalue":{"value":{"amount":"+0.8783500790596008","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":"Q805628$00C77126-56FC-472D-9BB1-5D84A860D2DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fc2e951b7231c438a533d23fc6b06aac7ea5cfc","datavalue":{"value":{"entity-type":"item","numeric-id":2563506,"id":"Q2563506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2f187e9de542f4faac1a09289567fa9b1490873","datavalue":{"value":{"amount":"+0.8554491400718689","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":"Q805628$CC758768-AAE8-439E-81D1-E1017C8AA30A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ff5998dd4e291a43bee96a487ebfab3295ccda2","datavalue":{"value":{"entity-type":"item","numeric-id":1878594,"id":"Q1878594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f077f7ea0873864d10aa1537bf0900ccf1b1b7f","datavalue":{"value":{"amount":"+0.8543351292610168","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":"Q805628$5F2490CA-814A-48FE-BFB1-D23A581A9848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b52e6e60e352b8209cb9752544be9efa50f9a706","datavalue":{"value":{"entity-type":"item","numeric-id":950329,"id":"Q950329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad419e698b8ef09a1b1b959d164a17e22a52697f","datavalue":{"value":{"amount":"+0.8538042306900024","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":"Q805628$CE32609D-84F8-45E8-98EB-819011796DFA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:805628","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:805628"}}}}}