{"entities":{"Q932657":{"pageid":934505,"ns":120,"title":"Item:Q932657","lastrevid":65477445,"modified":"2026-04-12T02:51:51Z","type":"item","id":"Q932657","labels":{"en":{"language":"en","value":"On the minimum degree forcing \\(F\\)-free graphs to be (nearly) bipartite"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5300656"}},"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":"Q932657$F24AE05F-B532-4563-BB37-CFBE6ABA673E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1084195d4971eed90ef4907b1fb7cf31f604f086","datavalue":{"value":{"text":"On the minimum degree forcing \\(F\\)-free graphs to be (nearly) bipartite","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q932657$93F5F72D-2930-42C7-A0D5-9ABE8E5B2DEA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2273237120157c069f239bb7d4aebb1504fea143","datavalue":{"value":"1149.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932657$B7F1B0C5-4E1F-44D8-B8DE-8305CDFADCD8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93a3904bbec182d67e761f38904a81bb2531b67d","datavalue":{"value":{"entity-type":"item","numeric-id":178704,"id":"Q178704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$35D295E9-DBA5-4707-BE62-21E15F358F86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a40a7c874481a1a229f505dcfb1443755c75490","datavalue":{"value":{"entity-type":"item","numeric-id":1175548,"id":"Q1175548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$0B41CD81-B991-41F8-848D-C258E0EDFEB9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$BD7B40C0-07B7-40EE-A7B5-26B2EF93F99E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"37182800059ed633e356c0f78cd13f10c8c7f234","datavalue":{"value":{"time":"+2008-07-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":"Q932657$1134D754-4C8E-4EEB-BDB7-1C4BB11C1869","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8d0c98c1eb649b01039064f588c2a8c47e8611af","datavalue":{"value":"Let \\(\\beta(G)\\) denote the minimum number of edges that can be deleted from \\(G\\) that results in a bipartite graph, and for a \\(3\\)-chromatic graph define \\(\\xi(F)\\) to be the maximum \\(k\\) such that \\(F\\) can be homomorphically mapped into \\(C_k\\) for \\(k\\) odd. This is denoted by \\(F \\rightarrow C_k\\). It is shown that for every \\(\\alpha, \\eta > 0\\), there exists an \\(n_0\\) such that if for every \\(F\\)-free \\(G\\), where \\(F\\) is \\(3\\)-chromatic, \\(G\\) has at least \\(n_0\\) vertices, and \\(\\delta (G) \\geq \\left\\lfloor (2n)/(\\xi(F) + 2) \\right\\rfloor + \\eta n\\), then \\(\\beta(G) \\leq \\alpha(n^2)\\). It is also shown that for every \\(\\alpha > 0\\), there is an \\(\\overline{\\eta}> 0\\) and an \\(\\overline{n}_0\\) such that every \\(F\\)-free graph \\(G\\) of order \\(n \\geq \\overline{n}_0\\) and \\(\\delta (G) \\geq \\left\\lfloor (2n)/(\\xi(F) + 2) \\right\\rfloor - \\overline{\\eta} n\\) contains a subgraph \\(G'\\) with at least \\(e(G) - \\alpha n^2\\) edges such that \\(G' \\rightarrow C_{\\xi(F) + 2}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q932657$FF06C635-527A-4547-97F3-4DA1C23CEAB3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932657$7AF5B283-BFA6-4C02-B921-34B61C910CA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932657$7D3D17CE-DAF8-4AA4-AE1B-ECD99F37EC29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932657$E6C11339-0BF7-4B6E-8503-355DD5F86ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932657$EEF11746-43F5-4D25-8565-B45D2FE52F74","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b799ab73bee6e328c2488bfc19dde22efa320061","datavalue":{"value":"5300656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932657$20F0DF68-5276-4BA3-8E9E-49F40151108E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013a665df3872df6518b386ba286fc369d4eed69","datavalue":{"value":"extremal graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q932657$03968854-B291-4408-AC42-4BD7318A924C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eecb173004633ca38efc326bcd073800d8b745c9","datavalue":{"value":"bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q932657$1DC67DEC-71A8-4A10-8E56-F0495B2531C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"877406d33b02b093a509cd6008cc8a24cb2d0530","datavalue":{"value":"odd cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q932657$22F98E7F-9EFC-4EC7-8AE1-719D0952C147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q932657$64CD6166-0038-41FD-BDAF-91CE8898E117","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":"Q932657$2D2B2C39-C273-4D45-8F7D-E39B6434F128","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":"Q932657$233F9DB5-15A7-49A7-B34F-64527211805C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"31f220a26bfb6aaacda5cf8f602865d68d3369ef","datavalue":{"value":"https://doi.org/10.1016/j.disc.2007.06.047","type":"string"},"datatype":"url"},"type":"statement","id":"Q932657$2163B4A9-BB56-4FE0-9BF3-50B8CF071349","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"21378dfc26c5647d625c03fd6b2d2b92850984b9","datavalue":{"value":"W2158274269","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932657$280886AE-6AD8-4987-AA10-2D82E83B55C1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a68f6924f4911fb107a546ad9848f55b61652de","datavalue":{"value":{"entity-type":"item","numeric-id":1844683,"id":"Q1844683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$76C23AE0-8B75-4744-A534-27E350F35198","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":"Q932657$CCE9A862-9D3B-4CAB-A6C7-5FD9344965BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6da70f99fd4cf6ae4ab94d8010048be644fea36c","datavalue":{"value":{"entity-type":"item","numeric-id":5567712,"id":"Q5567712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$458B9D02-5EA3-42DA-9B8A-5E033702167D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03ef46efd22e4c58a8ba7f3f8e6dd19d883363a6","datavalue":{"value":{"entity-type":"item","numeric-id":2562797,"id":"Q2562797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$F1F9C7CA-043C-4288-BB0A-A576A019C980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b79004eec82002fc898d57feecbac5016d092acd","datavalue":{"value":{"entity-type":"item","numeric-id":5842850,"id":"Q5842850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$BB19B61E-6515-4CD4-B173-68622122C107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d28e089c48fffbbadad939afc4e63adefc06c727","datavalue":{"value":{"entity-type":"item","numeric-id":1412666,"id":"Q1412666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$96CE19FC-5262-4F84-B14E-42D2999B4F33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"887ce430b000ffd8813e06446b140ace91a67a26","datavalue":{"value":{"entity-type":"item","numeric-id":5548826,"id":"Q5548826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$A22C0D4A-E000-4C9E-90B3-65D83798C7FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b19aad2c9a72e95f9350690ebb4e9aac1c6c708c","datavalue":{"value":{"entity-type":"item","numeric-id":3312262,"id":"Q3312262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$98800DA3-61D5-4BB0-AD27-F93394DBA227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"145548e851f720be1018123065c516a7e020cf39","datavalue":{"value":{"entity-type":"item","numeric-id":5689007,"id":"Q5689007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$9B82BB98-3523-479B-8B6A-A1ED8AFF15C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"922598857b64c682415741da5fd4eb7cb848d71b","datavalue":{"value":{"entity-type":"item","numeric-id":4200109,"id":"Q4200109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$39B8D31F-5676-4515-8F07-B6DF33DF9BE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe979badcb8bfb7a41b5de5f764eb66747617dd","datavalue":{"value":{"entity-type":"item","numeric-id":5781249,"id":"Q5781249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932657$2DC739A4-6EFC-4E50-B9B5-BEEDAC8FC4D9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b7c3b39ee3c1e0b3ea3bcbfb1f7dadbd2b11e327","datavalue":{"value":"10.1016/J.DISC.2007.06.047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932657$E7073970-E94E-48A4-AD9C-499B72965618","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"955df49b887b7aa41f67fa7d403192166e27c0b3","datavalue":{"value":{"entity-type":"item","numeric-id":805628,"id":"Q805628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebc82e830f4491989fd4e6354f856c5da2389698","datavalue":{"value":{"amount":"+0.8073256015777588","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":"Q932657$25C3E1E3-A123-4CE8-BB3A-D7C54F40EC9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0eef9c13974daaba27a8d7599c7dd7dbccf382ea","datavalue":{"value":{"entity-type":"item","numeric-id":819178,"id":"Q819178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14e4fffdca9f4f026125f1347e3b7ee6ff05044c","datavalue":{"value":{"amount":"+0.7772437930107117","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":"Q932657$930512F7-17FA-4B26-A430-FC96451B25A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d3239c7d8924e46b0711fddf7f113bbfe8cbafe","datavalue":{"value":{"entity-type":"item","numeric-id":1412666,"id":"Q1412666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82d1456cd8286765cc4ac790841d390ebb3c9e3b","datavalue":{"value":{"amount":"+0.7762373089790344","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":"Q932657$F7502B1E-CD3B-4D0B-BAEB-7EEF229FE987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c33da9cae193a068efcc82b7880e9938d0dc512d","datavalue":{"value":{"entity-type":"item","numeric-id":859617,"id":"Q859617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69ab4b9043a019d619684cf2637c92e7160feb52","datavalue":{"value":{"amount":"+0.7734741568565369","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":"Q932657$B4F0AB2C-8604-4DE5-BA85-97FEC959295D","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":"d41dd87f1c373b4c167bf66d4963b1cbcc5db01c","datavalue":{"value":{"amount":"+0.7723132371902466","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":"Q932657$BB9F63AE-8B3B-446D-822B-33435CCD570F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the minimum degree forcing \\(F\\)-free graphs to be (nearly) bipartite","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_minimum_degree_forcing_%5C(F%5C)-free_graphs_to_be_(nearly)_bipartite"}}}}}