{"entities":{"Q490312":{"pageid":492079,"ns":120,"title":"Item:Q490312","lastrevid":62228886,"modified":"2026-04-11T04:39:30Z","type":"item","id":"Q490312","labels":{"en":{"language":"en","value":"Maximum 4-degenerate subgraph of a planar graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6389250"}},"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":"Q490312$F5AAACC8-A3EA-4D61-9FBA-381D17E99771","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6cc772b6e162a885f3f2d44924c0b9f7642ab25a","datavalue":{"value":{"text":"Maximum 4-degenerate subgraph of a planar graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q490312$DCF10BF3-2DFE-40DD-A8EF-732E18A017F9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4e1dc8375736f0a3c5eaf4e5b020c880e72e1cd1","datavalue":{"value":"1305.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490312$E68B1747-C90A-4B2D-AD2C-3FFB543C28C2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aaf718c5b28e0f5126a78ca32045d5bdb8e5e3ad","datavalue":{"value":{"entity-type":"item","numeric-id":490311,"id":"Q490311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490312$F42071CC-800C-44E0-BF7F-32C536F15230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4de98dec7d2fd0e5763b9d7af3bb9f2f0ccf94c","datavalue":{"value":{"entity-type":"item","numeric-id":383684,"id":"Q383684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490312$7364EB95-C9A9-4E17-A75C-F87BC94B0558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6b19b09c7519f38384d021f845694abb1cfab04","datavalue":{"value":{"entity-type":"item","numeric-id":168189,"id":"Q168189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490312$F9BCB7D7-4C13-4F32-BD93-9A5AB003FC57","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":"Q490312$EC1425A8-84EE-4950-93EB-FA2F513AD5F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8bb6c16b18fb3fcb7c20a96f2fcd94ae71f0f929","datavalue":{"value":{"time":"+2015-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q490312$9ED8BDA6-302F-4ED2-8725-2972AECF8E96","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ee11db4e8546c26bbcd4247f67038c380c4b1520","datavalue":{"value":"https://arxiv.org/abs/1305.6195","type":"string"},"datatype":"url"},"type":"statement","id":"Q490312$487A4944-4662-4C72-8C23-F9EDDC47D88A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"de32561e8c3a4dcc3f4ac3109b4d44feff78dba2","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p11","type":"string"},"datatype":"url"},"type":"statement","id":"Q490312$668EDA8E-1E3C-4B6B-83AC-FA0ED75FDE9B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0967a029c7cdfc2e779374687f381c558c959366","datavalue":{"value":"Summary: A graph \\(G\\) is \\(k\\)-degenerate if it can be transformed into an empty graph by subsequent removals of vertices of degree \\(k\\) or less. We prove that every connected planar graph with average degree \\(d \\geq 2\\) has a 4-degenerate induced subgraph containing at least \\( (38 - d)/36\\) of its vertices. This shows that every planar graph of order \\(n\\) has a 4-degenerate induced subgraph of order more than \\(8/9 \\cdot n\\). We also consider a local variation of this problem and show that in every planar graph with at least 7 vertices, deleting a suitable vertex allows us to subsequently remove at least 6 more vertices of degree four or less.","type":"string"},"datatype":"string"},"type":"statement","id":"Q490312$F11EA097-13EF-4E3D-B96D-4C6DB4821F18","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490312$D7413DDA-E4CD-41FF-9623-1989EA51F351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490312$C366048F-ACC2-4E6F-8734-42C714784F0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490312$469CA53C-6FC8-4668-B4C0-AF8C1C8E7AE6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"86dcb0e798f48edfd833281362dcd89ba7271e39","datavalue":{"value":"6389250","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490312$73E17F32-132E-4DFA-A778-908BE309295C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"703e46efe0d88597983fe59b5140e2dce87cc1d7","datavalue":{"value":"degenerate subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q490312$8B4B9975-97AC-4CAB-9A90-FCA039B1F1A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q490312$CB631A4C-7279-4870-9CBE-23A680A85B47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d7cda7b7bce8f5ee07c238e9cacb71a3a96be7d","datavalue":{"value":"list colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q490312$D388BDCA-3378-4381-BBE6-2FCFAB44AB78","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":"Q490312$6A3D673F-6A8C-4C02-B0EB-BA922DE9B7F8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e24c1f3abeac7a85848c686b9ccd0c7e0b58d1eb","datavalue":{"value":{"entity-type":"item","numeric-id":1092059,"id":"Q1092059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490312$4540EE35-3ACD-49B9-9771-9182746B77AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd1d33eef438960b51608343184177f3ebc4d421","datavalue":{"value":{"entity-type":"item","numeric-id":665753,"id":"Q665753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490312$5E20B2D0-96F2-415B-9AFF-C6217A242ACB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"378cb32fedebbb04e30f06b7e1bef560c306dd6d","datavalue":{"value":{"entity-type":"item","numeric-id":4137202,"id":"Q4137202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490312$81138E01-FBAA-421F-B7BA-853952D5175F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3529de846b9c1c2f66dc361e6c821a6cb47ba82","datavalue":{"value":{"entity-type":"item","numeric-id":4797463,"id":"Q4797463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490312$3D912328-C24F-4CED-9DB9-1E81F92C6451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef1e280ff313784cce95cf1dc6e1b139af0e3310","datavalue":{"value":{"entity-type":"item","numeric-id":5599569,"id":"Q5599569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490312$9D6E107C-4AC0-4FD0-8626-2EF5C7D83B7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8e9a01d057f2ac8669e7cac2ad5d67b6775d2fa","datavalue":{"value":{"entity-type":"item","numeric-id":1333334,"id":"Q1333334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490312$D24C7F77-25EB-4C9C-814E-150D49702AB2","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"24ba17441b659dd13094a717a2901cc76596a9a3","datavalue":{"value":"bafkreifhncqi6jekqmshl7eeykg24lbosywfhw3kbyp2c6frg4vbehjtqm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490312$4BD7DD3A-7CDA-4A6F-943A-1D91CEDF4CA7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19d0792bd7da6b43cf735126502821b7c8238350","datavalue":{"value":{"entity-type":"item","numeric-id":5419975,"id":"Q5419975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e242c0cee8b24d2ea926a797d957d8569e4b9d4","datavalue":{"value":{"amount":"+0.9233620166778564","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":"Q490312$9A1B6B8E-BFDB-4C35-B6F1-05984E88BCCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a339e1b02f6b7308a8280c4719f03c0deda1313","datavalue":{"value":{"entity-type":"item","numeric-id":6056810,"id":"Q6056810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b33711fa668381e3eb05a796d31664759770af8c","datavalue":{"value":{"amount":"+0.8920645713806152","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":"Q490312$6D325DA3-F41B-49E4-AAE4-C734C6E27A2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95fa71ad63ee13c21f1c24f9fa794f58a92aaab8","datavalue":{"value":{"entity-type":"item","numeric-id":1092059,"id":"Q1092059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"049e668faa2d9c5ba53bea96b1cc03f6f65d0196","datavalue":{"value":{"amount":"+0.8918298482894897","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":"Q490312$6246FAAF-869B-45DA-AF42-CA4D75D227EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff48e3104fb0d774a42fc0594fddb2f6413ff258","datavalue":{"value":{"entity-type":"item","numeric-id":1753031,"id":"Q1753031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07158b0c26ff137073dc54e19c59518b2ddf6555","datavalue":{"value":{"amount":"+0.8334300518035889","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":"Q490312$690E4FF8-DCC0-4D8B-8A6B-7AFDC011E4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6efcf9a5c683f6e9f47d7a9d26a7bfad17cb9ec","datavalue":{"value":{"entity-type":"item","numeric-id":1907105,"id":"Q1907105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9b1b0f122131212152d4e12b3a74621844947f9","datavalue":{"value":{"amount":"+0.8251528143882751","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":"Q490312$DAAF1F47-BEA2-4D02-BF8E-460E21AFCE6F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximum 4-degenerate subgraph of a planar graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximum_4-degenerate_subgraph_of_a_planar_graph"}}}}}