{"entities":{"Q1322210":{"pageid":1332960,"ns":120,"title":"Item:Q1322210","lastrevid":70707267,"modified":"2026-04-13T16:16:18Z","type":"item","id":"Q1322210","labels":{"en":{"language":"en","value":"Lower bounds for constant degree independent sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 562615"}},"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":"Q1322210$79D3D8B6-64D8-4319-B76A-1212354875D1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1093d7bd87a283fbdd93b9793274ef03f2ebf6d6","datavalue":{"value":{"text":"Lower bounds for constant degree independent sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322210$61777BAA-BC6C-42CF-BB5E-69B1C31999C4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"84ecb20024088df3249c623ec3b818ee3732620e","datavalue":{"value":"0799.05031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322210$5D24E3FA-ECE5-4628-B2B0-EC86272F9C84","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bc6bf4efbd69682b3fb62a297dca3db1b2ce2eed","datavalue":{"value":"10.1016/0012-365X(92)00463-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322210$B6E16CD3-12C0-4530-B9CC-ABFDEA52EFA2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"82040cfe7ba0d41798d213a2940864deca0691a1","datavalue":{"value":{"entity-type":"item","numeric-id":186192,"id":"Q186192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$F73454BB-FC2C-4084-B9C4-1A2B4326394F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa51bb1863efa081b3dbaf456d6e3c11d5750efc","datavalue":{"value":{"entity-type":"item","numeric-id":709321,"id":"Q709321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$D319358B-8CF9-49D8-BEFD-CF26D0856CAD","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":"Q1322210$F98E9CA3-8081-4519-8633-6C182BFBA705","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7a269f34123f780c17e245cbaab12f8ee5852e5b","datavalue":{"value":{"time":"+1994-11-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1322210$D4EBB81A-843F-4917-A507-B572A6A8C6DC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ca40c01c839cc342516815f8f1b15ee69c8c8d5","datavalue":{"value":"Suppose among the set of vertices of a graph of degree \\(j\\), we select the independent set of largest cardinality. Denote this cardinality by \\(\\alpha_ j\\). Let \\(\\alpha^*\\) be the maximum over the \\(\\alpha_ j\\). The paper proves the following results about \\(\\alpha^*\\), where \\(v\\) is the number of vertices of the graph: (1) For any tree, \\(\\alpha^*\\geq (v+ 2)/4\\). (2) \\(\\alpha^*\\geq v/{\\Delta+1\\choose 2}\\), where \\(\\Delta\\) is a graph's maximum degree. (3) For a maximal planar graph, \\(\\alpha^*\\geq (3/61)v\\). (4) For any planar graph, \\(\\alpha^*\\geq (2/65)v\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322210$924400A9-A8A3-489D-8AFB-70E92B8FA75A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"61cf9dfec5b66ba829a3bd08d983df202add1f13","datavalue":{"value":{"entity-type":"item","numeric-id":801083,"id":"Q801083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$D2C5EF3F-D1A2-41B7-96E3-19EA7A5583A2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322210$80A88AEA-B168-4DC5-832D-ED65AA07F06C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322210$71FAFC9F-03C7-4042-8D9A-384C85CA4ECA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c0954dc955c6d862e44cc1b36e1fbd2526af51d","datavalue":{"value":"562615","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322210$16AC1C77-5469-4DF4-B4A1-9E00EEC321E7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b77b431fc86a92792dc6a21fc772bba2088fb678","datavalue":{"value":"bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322210$CDBB21F2-C352-464A-B2F8-D393598F8057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"308cf63ea8c077f8633f0af8aef370fde0dd7b99","datavalue":{"value":"degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322210$95EEECE7-FEF2-4B90-99CC-2AF5491D6DC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322210$635556FE-784F-4B24-A0AA-0D16C575199E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322210$8D0A11C6-8146-4698-8539-A72606A92BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322210$EDAF5B68-0F8E-414F-B3B2-60ACFAB52E01","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":"Q1322210$A6496C3C-2CF3-4887-A5C2-EA3A3A9A0BB5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b79832c576a26410f6de23f73ccb9d64a38218bb","datavalue":{"value":{"entity-type":"item","numeric-id":4845644,"id":"Q4845644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$E4AD502C-A94E-4A79-9290-6A03B9A11A7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86187cd049bd6565ddbc4e21f37dc55f378bee76","datavalue":{"value":{"entity-type":"item","numeric-id":1250223,"id":"Q1250223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$9FCF6A91-0FE3-486D-9F82-0676CE3F9FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63ce408a109a0f787c113b8dd93aa6eed7ab084c","datavalue":{"value":{"entity-type":"item","numeric-id":1250224,"id":"Q1250224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$A92FAC2F-06E4-498F-9E01-263DC7FA91FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$BD31D7A9-29BB-429D-8952-9577CFDDC25A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$EBF62FD9-5986-481D-9305-CCBACB4CC089","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf6dd27ad1e0108f4014296aa58a9a489aabf84c","datavalue":{"value":{"entity-type":"item","numeric-id":1835927,"id":"Q1835927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$5DB3C931-8EC4-475E-821D-F281701C9276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ef5cda04435da0bf4e7f37f3e8c3ef5056ff078","datavalue":{"value":{"entity-type":"item","numeric-id":3777423,"id":"Q3777423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322210$04C4A712-F3CB-4D04-82B4-75601A8B5FD7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1c1f988199d38064255e8328142d8221dbf5c61","datavalue":{"value":{"entity-type":"item","numeric-id":548268,"id":"Q548268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c82ce8fe16930eeaed68b68574e9200129de4b14","datavalue":{"value":{"amount":"+0.93333447","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$49E8FE4F-8436-4CEF-80BC-E2BAB43C8F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9eec050680630e4d2709574daca509394b1ac45","datavalue":{"value":{"entity-type":"item","numeric-id":4636626,"id":"Q4636626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df5ed80c64aff54516c64a492ac774ee5f536524","datavalue":{"value":{"amount":"+0.9251319","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$98DD0E26-A260-4229-8252-64D34D97B048","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20ed3246efba1c35f405ea494a44d5dc0967aca6","datavalue":{"value":{"entity-type":"item","numeric-id":4873224,"id":"Q4873224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2669c4b3b74d383256360c37ad0abd9ed900260b","datavalue":{"value":{"amount":"+0.9162658","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$9EE3D4E3-1B73-408C-AD99-97E8048EF9C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9eed126a7e23f5f2fe89697579ff8fad2118bc84","datavalue":{"value":{"entity-type":"item","numeric-id":5437226,"id":"Q5437226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29c491411099735de2f48e3d007c5511e24b65ee","datavalue":{"value":{"amount":"+0.9036066","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$C37FC778-B15B-4F26-99AC-1B85CCC66190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"461c6edfb33b36ee0e4bef8d8ec584613a4cb3db","datavalue":{"value":{"entity-type":"item","numeric-id":260061,"id":"Q260061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b40f95ae437b22ba5faf275def78dad674d3f57","datavalue":{"value":{"amount":"+0.89354265","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$ABA539BE-0E1A-4D16-BF4F-E8530EAAA291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9487f0df34d3e846d8b6469c45b7faee57d78a8f","datavalue":{"value":{"entity-type":"item","numeric-id":1026137,"id":"Q1026137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"837636db48059627fc77bcaa255a5633ced22795","datavalue":{"value":{"amount":"+0.89301044","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$38ADF6C4-3B07-43DB-AD9E-FBE03CC25236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08852b6e6207e9d08f70178a45a40d323a154f09","datavalue":{"value":{"entity-type":"item","numeric-id":3603532,"id":"Q3603532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"837636db48059627fc77bcaa255a5633ced22795","datavalue":{"value":{"amount":"+0.89301044","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$89A35462-7467-405E-AEB4-6D5C8C2D692C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"955aee3ab14833c1132944179d36c4724ef42a0d","datavalue":{"value":{"entity-type":"item","numeric-id":2934676,"id":"Q2934676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94b31b8639373c6e2fd69d8d05fa34d3e3440140","datavalue":{"value":{"amount":"+0.8864207","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$08A03A94-FDE1-4317-BD5E-55E34F440DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5369bf51a3753313ef23ddd6da4f69db023058f6","datavalue":{"value":{"entity-type":"item","numeric-id":1584341,"id":"Q1584341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fc640e6e5702d09e32e1eed6777f45bc4bdd2b9","datavalue":{"value":{"amount":"+0.8863737","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$0CFF6D69-2F64-43B0-B3AE-252BB312F704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef10628d1ea4134f11c0639431ca2408223afccc","datavalue":{"value":{"entity-type":"item","numeric-id":4237730,"id":"Q4237730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"809b7acc121b67ecabc8f490078fb061c74c6b0d","datavalue":{"value":{"amount":"+0.8847764","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322210$E11B170F-2F63-44AA-858B-CC4EA8A75417","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds for constant degree independent sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_for_constant_degree_independent_sets"}}}}}