{"entities":{"Q405242":{"pageid":407009,"ns":120,"title":"Item:Q405242","lastrevid":61642869,"modified":"2026-04-11T00:40:07Z","type":"item","id":"Q405242","labels":{"en":{"language":"en","value":"A note on independent sets in graphs with large minimum degree and small cliques"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340205"}},"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":"Q405242$E299DBA0-84EF-4F37-A8B2-F75F8DA5E708","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fe0e8b1f587517feaf46bf4aea602a35d0419960","datavalue":{"value":{"text":"A note on independent sets in graphs with large minimum degree and small cliques","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405242$16F5A95D-EB69-4C04-846C-E82CE0917152","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"972df5e1b948dcd85908c06f9fea1dd509e7596c","datavalue":{"value":"1300.05232","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405242$2DA435CB-9AB2-411D-886F-0658A135D4A5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b31abc40c3990c9b61473c6aa3ac80b6d3ac309","datavalue":{"value":{"entity-type":"item","numeric-id":405241,"id":"Q405241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405242$0CC005C8-D62A-416C-8A6E-22A2125D0583","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":"Q405242$77B54E04-8697-4FE5-AA6F-1F3360C78567","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405242$F9805664-8735-45D1-B906-8D6769AFBE0A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6f9d66624f5fd36572434cd8dbe79e9a36bd629a","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p38","type":"string"},"datatype":"url"},"type":"statement","id":"Q405242$83695FE9-C9A8-4C75-9C9E-E534CC7DF191","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dd94d8f42b1f18292eca3b58b625e66efbcc446f","datavalue":{"value":"Summary: Graphs with large minimum degree containing no copy of a clique on \\(r\\) vertices (\\(K_r\\)) must contain relatively large independent sets. A classical result of \\textit{B. Andr\u00e1sfai} et al. [Discrete Math. 8, 205--218 (1974; Zbl 0284.05106)] implies that \\(K_r\\)-free graphs \\(G\\) with degree larger than \\(((3r-7)/(3r-4))|V(G)|\\) must be \\((r-1)\\)-partite. An obvious consequence of this result is that the same degree threshold implies an independent set of order \\((1/(r-1))|V(G)|\\). The following paper provides improved bounds on the minimum degree which would imply the same conclusion. This problem was first considered by Brandt, and we provide improvements over these initial results for \\(r > 5\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q405242$D82CAAA6-141A-4B89-BC04-62E3CE4338C4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405242$B9CD4D3C-377C-44B7-BCEB-392AADACBF83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405242$85AB6D4B-F85A-497F-8D4E-9A29511DF21A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405242$A5C74742-5F29-4592-BB26-8286A4CFF4B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405242$A5EF234A-5FC3-4FB9-ACB0-B90D5A0DD3D7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"784711ea395b0dbed8e1a77f38afb6f5b988b90f","datavalue":{"value":"6340205","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405242$32775975-1B05-468A-914D-4A59095413E3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d945464ea52d0483fab7a868292502c1a49c4dc","datavalue":{"value":"dense graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q405242$ECD71078-A128-4E3C-955D-41447189F8EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9890d2d31de82fcf86b74b799289b36efeaabea2","datavalue":{"value":"independent sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q405242$A8BCCF93-C41B-4BAD-9EF4-74CC22E7B560","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":"Q405242$266BFE28-4C0E-4827-BD6B-9F5D2CB75C6E","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":"Q405242$96F85877-C0A3-4283-8034-BF86024512B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fedc9bd46cbfbd02a4c1e2a3de6d7634cfb748d1","datavalue":{"value":{"entity-type":"item","numeric-id":1229891,"id":"Q1229891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405242$080A20F7-B76F-4DDB-A061-8DCFFE76D7FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"946eab647e7fbf1e29c6d650f830c04fd8715dd4","datavalue":{"value":{"entity-type":"item","numeric-id":1878828,"id":"Q1878828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405242$8F605C6A-E28C-478A-BE25-422E269A7326","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":"Q405242$3238DDE3-3333-4241-961D-7CA8BA28F3B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3223e2f31109bbacecb2aefb278f0d2236491841","datavalue":{"value":{"entity-type":"item","numeric-id":858147,"id":"Q858147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405242$728630EE-306B-4F3C-8D62-CD2F4CA0C5DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c77d9a5ccbb51cfd973fe17b65cc5e8c1a26e68b","datavalue":{"value":{"entity-type":"item","numeric-id":4401979,"id":"Q4401979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405242$990FA671-F04A-448C-8C92-9F925FC61AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2317dda92a8556b6038d60189c37b94b8d462401","datavalue":{"value":{"entity-type":"item","numeric-id":1410410,"id":"Q1410410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405242$4603DDC8-9F1E-4153-BE7B-A06C8089296B","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":"Q405242$2D9D6E7F-E85E-4EE7-B7DE-4B1E97A88AD7","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"322f6cfa3d4c0897e031358a8d66db980ba35d81","datavalue":{"value":"bafkreiawpjyr7trl4bonred2iv6pj2rtpddnpztfzm3ikjrkcmbpbxwnbu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405242$EE919D68-BF5B-4A94-A324-D45115603143","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2abd3d4649e02f75461854cd9532bfcdab8da4c","datavalue":{"value":{"entity-type":"item","numeric-id":3168661,"id":"Q3168661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae4e4bedc5a8bb6fef857d2d7a624ce98f8e4767","datavalue":{"value":{"amount":"+0.8093391060829163","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":"Q405242$579C173A-9AD2-49F2-873B-B8090582E6BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a5cc43289a80076ebd4b26e36315462ed940d6a","datavalue":{"value":{"entity-type":"item","numeric-id":1998757,"id":"Q1998757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"028e42444f762ce43268089caeade37e5f5ef133","datavalue":{"value":{"amount":"+0.7973244786262512","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":"Q405242$A3B935FD-3B85-42DD-AB30-52C92356DAB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9a876b29b1e7a27e2cefd6e55ac08bdb828f9a7","datavalue":{"value":{"entity-type":"item","numeric-id":4271613,"id":"Q4271613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0036fc0bf2b7cd85dc6f099284d08e7d4623fbe8","datavalue":{"value":{"amount":"+0.7962422966957092","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":"Q405242$4AFFFC13-7BCF-4214-B988-C9BBFA4664C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4456078534c9bfd503f15e8a9cb3ff6dd4847d1","datavalue":{"value":{"entity-type":"item","numeric-id":1878828,"id":"Q1878828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb26beeb73d213caadc489b454a95ecf03121ad4","datavalue":{"value":{"amount":"+0.7923497557640076","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":"Q405242$D41B1A53-8971-4481-84D0-61EEF5067D28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2ec4d1542b2e1725b3310997e282147ea021203","datavalue":{"value":{"entity-type":"item","numeric-id":5397737,"id":"Q5397737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ed556ff92973b8ec65ad8c4b3ce672898465bdf","datavalue":{"value":{"amount":"+0.7845215797424316","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":"Q405242$6F40FB0C-9E04-4BB6-8711-C575FF75A148","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on independent sets in graphs with large minimum degree and small cliques","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_independent_sets_in_graphs_with_large_minimum_degree_and_small_cliques"}}}}}