{"entities":{"Q1753010":{"pageid":1763752,"ns":120,"title":"Item:Q1753010","lastrevid":57533700,"modified":"2026-03-31T07:30:50Z","type":"item","id":"Q1753010","labels":{"en":{"language":"en","value":"Partitioning sparse graphs into an independent set and a forest of bounded degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6873089"}},"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":"Q1753010$C3DEC3C3-EBF1-4F6D-91E0-36D74850CA49","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"00f5199fcb87e6489e27842a11caf9b39ec1c48c","datavalue":{"value":{"text":"Partitioning sparse graphs into an independent set and a forest of bounded degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1753010$A45642C9-45E0-4780-A024-612B70933DBE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c7c408c1e20228123e9cf1ad83a87f164f72a866","datavalue":{"value":"1391.05091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753010$23F641FD-C33C-4FA0-8BDE-75D31A9514EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d22bd487e08e940d7dd9156276fda83f6864311e","datavalue":{"value":{"entity-type":"item","numeric-id":317408,"id":"Q317408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$0800B588-5834-4EC4-96EC-83D6AF8AA784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3fd2acd4c850efcd990f7986e7e150d8fca9a262","datavalue":{"value":{"entity-type":"item","numeric-id":317410,"id":"Q317410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$31236D04-AC87-4E64-9218-6B98D0D5A1FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e9731cfc25047c524a2a83588667b586efc613b","datavalue":{"value":{"entity-type":"item","numeric-id":274684,"id":"Q274684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$27122A7F-B4CE-47AB-8DFA-4C21C24F4DE5","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":"Q1753010$C221B768-BCBC-4C27-AC4E-C141A5F0BCE3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"889be0f8e7c5593fd9d724762872dd9608a4e49c","datavalue":{"value":{"time":"+2018-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1753010$289D4D2B-99F9-42A5-82E0-AAE578C68594","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52291614db05d672bf43af3d2d401876200ea9f4","datavalue":{"value":"https://arxiv.org/abs/1606.04394","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753010$615E1897-21BD-4FBE-82D3-63EF2CDA356E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"9272069ed877de468f9638605c10881f631d8220","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p45","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753010$5C451AED-4315-403D-8C90-4323B7222017","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"11139af5ca9a55dd74c8f392217471e2bfdb563e","datavalue":{"value":"Summary: An \\((\\mathcal I,\\mathcal F_d)\\)-partition of a graph is a partition of the vertices of the graph into two sets \\(I\\) and \\(F\\), such that \\(I\\) is an independent set and \\(F\\) induces a forest of maximum degree at most \\(d\\). We show that for all \\(M<3\\) and \\(d \\geq \\frac{2}{3-M} - 2\\), if a graph has maximum average degree less than \\(M\\), then it has an \\((\\mathcal I,\\mathcal F_d)\\)-partition. Additionally, we prove that for all \\(\\frac{8}{3} \\leq M < 3\\) and \\(d \\geq \\frac{1}{3-M}\\), if a graph has maximum average degree less than \\(M\\) then it has an \\((\\mathcal I,\\mathcal F_d)\\)-partition. It follows that planar graphs with girth at least \\(7\\) (resp. \\(8\\), \\(10\\)) admit an \\((\\mathcal I,\\mathcal F_5)\\)-partition (resp. \\((\\mathcal I,\\mathcal F_3)\\)-partition, \\((\\mathcal I,\\mathcal F_2)\\)-partition).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753010$EC7412A6-DA47-4E46-8545-D07AD92249EE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753010$6474066E-C60D-4827-A1C9-7CDF8939EF7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753010$A20EB192-877D-4F69-845A-F24279A26B4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753010$902EF072-9D09-4749-83A0-C6C5ABC645CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b54e07fa0399072ce73a540a4cbd7858c0d3f3cb","datavalue":{"value":"6873089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753010$312A9050-CCD5-44BC-A35C-F5D92B16492A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753010$E758EA50-F96A-4D7C-9432-7147BCC0F07E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d3fc3f306278971b47588c54be6220243123d7e","datavalue":{"value":"sparse graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753010$D134AA9B-05EF-490D-B73C-185EEF9B0D0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"023dc2dc5cdc9807b01a9388c29761acfb1e200f","datavalue":{"value":"vertex decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753010$6873FDAE-E964-4A55-863D-42A25B052AFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9890d2d31de82fcf86b74b799289b36efeaabea2","datavalue":{"value":"independent sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753010$480E279D-2A7F-424D-929D-16AD8087303E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab1b2d33963dc85c015ba353e197645da8b8601d","datavalue":{"value":"forests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753010$7B1BC202-2034-41E6-95CF-1D12B9B6203C","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":"Q1753010$A1917F35-A489-432D-AB8B-623A4FEC50F3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"564aff63c4748397563b54fd1bb33f076e8c32ba","datavalue":{"value":{"entity-type":"item","numeric-id":4978449,"id":"Q4978449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$9374C669-E1DC-4E0D-9128-1019CB9A10A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$9F21C4F9-7DB1-4ECB-BC9F-9C8DA120A241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85cfa63f67ed3743ed6d983c37c02f4185c5f671","datavalue":{"value":{"entity-type":"item","numeric-id":5811782,"id":"Q5811782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$717CB5D4-86CA-4BAA-90B2-083781BB51F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24740898104d4c73d726dfe5ed5c3a2648f291b3","datavalue":{"value":{"entity-type":"item","numeric-id":5821654,"id":"Q5821654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$7B932C3B-E291-49E0-A403-4FF073584EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b5a77f691c73d3cc84a775a0deb455c68b0dbbc","datavalue":{"value":{"entity-type":"item","numeric-id":3241662,"id":"Q3241662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$F0433AB0-CEEC-46E9-A386-502191539953","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9150c1ba755fe333895308041f1399017d39139a","datavalue":{"value":{"entity-type":"item","numeric-id":5340529,"id":"Q5340529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$63E9256D-BBF2-47A7-A5D2-D325FED3EC47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c77678f211bbe5400ee4fff64f3c83ca35a084d","datavalue":{"value":{"entity-type":"item","numeric-id":4052157,"id":"Q4052157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$BE9519AE-0265-4843-8C85-5DD528008530","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f08c5112edf7f837490d497bb2f3820e4c72b45","datavalue":{"value":{"entity-type":"item","numeric-id":5732334,"id":"Q5732334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$3C3DD01E-48F6-41D0-B0D8-CE7F2029D060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cec1957a80454b28e1a4956848445bba3332200e","datavalue":{"value":{"entity-type":"item","numeric-id":4873220,"id":"Q4873220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$0CBC5CEB-2D6D-49DB-864A-58B14D521A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c2a94903479e9aeb3692183810e4827037bf66f","datavalue":{"value":{"entity-type":"item","numeric-id":2555085,"id":"Q2555085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$8C6D2364-510E-4763-AE9B-A1955C52830A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ec3dc3a44ac90b481428356217258d9af116d72","datavalue":{"value":{"entity-type":"item","numeric-id":2822589,"id":"Q2822589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$9FB5DB23-EA4A-401F-8D02-A9AAE37D5515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a11e1c6e2937547bc54475badf8ff832e9dd7a16","datavalue":{"value":{"entity-type":"item","numeric-id":2563172,"id":"Q2563172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$4EF427C5-C83C-481B-B83A-311225855E8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"779f2ad12863a733bf0d284d9407a8b122f663eb","datavalue":{"value":{"entity-type":"item","numeric-id":759160,"id":"Q759160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753010$1E6369CE-9FEC-48B5-8C7B-3376E40A63B4","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"71735bfe8063b8e3c1436dcaa27a640671dbfc09","datavalue":{"value":"bafkreiaslsuhyrkx3jnvp334uypcdp6hryamqs5htk2gdgi4fiquhkr2ca","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753010$49793361-D7ED-444E-BC6B-741D8A1D8977","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1833da697608c14bc0da92fd8ad4986691a21064","datavalue":{"value":{"entity-type":"item","numeric-id":2423361,"id":"Q2423361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33bd7e3b2cb1f74db51baadad1bf96d2ae7a1341","datavalue":{"value":{"amount":"+0.9272231459617616","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":"Q1753010$32A0C75D-2CA4-481E-8F49-F3C600CF2161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec978e5143e91a96d685ea850ebdfc8cf9ee4fad","datavalue":{"value":{"entity-type":"item","numeric-id":2185923,"id":"Q2185923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d2f02c648235192283e80299851f0be964393de","datavalue":{"value":{"amount":"+0.8995322585105896","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":"Q1753010$69194674-67A5-4661-A337-66A246A277A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff4b99a1f3cdb5d3e7f831f3851b54e2e6b85050","datavalue":{"value":{"entity-type":"item","numeric-id":5009333,"id":"Q5009333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c121f9059dc9a325842669a9de2044fd02cf75c3","datavalue":{"value":{"amount":"+0.8583458065986633","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":"Q1753010$63526857-6757-431C-92F2-AA7DC8073384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"722ca604c86c4f89d63941428081cd52403161a4","datavalue":{"value":{"entity-type":"item","numeric-id":2294901,"id":"Q2294901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"142befca39514d4a30a37c6381694417bdb58eb0","datavalue":{"value":{"amount":"+0.8463388085365295","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":"Q1753010$37734FF3-9DCC-459F-B5C8-4ECF90E4C86F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1753010","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1753010"}}}}}