{"entities":{"Q1898730":{"pageid":1909472,"ns":120,"title":"Item:Q1898730","lastrevid":69228834,"modified":"2026-04-13T05:37:15Z","type":"item","id":"Q1898730","labels":{"en":{"language":"en","value":"11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 798757"}},"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":"Q1898730$A94BCC25-3632-43E2-85DD-57ABEEB9048D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"82aa15ba21c0cacd0ead02c5606eb87be0b098b9","datavalue":{"value":{"text":"11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1898730$C35597DA-7E89-4ABD-9E61-980CD016FC8A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"303507e6ac814594ecfb335ed6b742b36b2ec826","datavalue":{"value":"0828.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898730$E2803EA0-C208-4041-A506-38C5DE0A1D5F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1200a2d2d33048b8518da57e6ed180fe561cbeab","datavalue":{"value":{"entity-type":"item","numeric-id":1385341,"id":"Q1385341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898730$00709566-7AB2-4334-B939-0D953D14BCC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb60b8d918936ffdb2c353fc0cd93cf62f2a7514","datavalue":{"value":{"entity-type":"item","numeric-id":583083,"id":"Q583083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898730$939E556C-111E-48C6-B2D6-BBEE0B61D170","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898730$7204CEE4-A3CC-45C0-81C5-EF3BF8972AC6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"771c3d65e511c1c23ff132299f8716909a176f01","datavalue":{"value":{"time":"+1995-12-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1898730$E9D0A753-1AF7-4BCA-AB79-9EC1BD688C77","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab7755804d77a01301f777b7f3ca2802b251ca76","datavalue":{"value":"Staton proved that every 3-regular triangle-free graph has independence ratio at least \\({5\\over 14}\\) and displayed a graph on 14 vertices which achieved exactly this ratio. We show that the independence ratio for connected 3-regular triangle-free graphs must be at least \\({11\\over 30}- {2\\over 15n}\\), where \\(n\\) is the number of vertices in the graph. This is strictly larger than \\({5\\over 14}\\) for \\(n> 14\\). Furthermore, there is an infinite family of connected 3-regular triangle-free graphs with independence ratio \\({11\\over 30}- {1\\over 15n}\\), limiting much further improvement. The proof will yield a polynomial-time algorithm to find an independent set of cardinality at least \\({11n- 4\\over 30}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898730$1F07A741-ADCA-4261-8D47-F672F356B6AE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898730$1DE8427C-A70D-4A7B-81DE-3A187E689DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898730$11341E8F-425A-49D0-AA17-BBF1D372E2E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898730$08B6B6D9-7BFF-4426-926D-ECBA40C68089","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a44a9b1e17d3a1714c00636b926c26daa4e45727","datavalue":{"value":"798757","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898730$0D91A1A2-A3B2-40DD-8E98-127FF73F5112","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a057adcafce0ab8f2d754597f48b98bb5d6180e","datavalue":{"value":"3-regular triangle-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898730$79FDB265-E814-4A17-8996-92FBE83CBCCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb86239c4da0c03bdf2c2d94d1bcbb3e23709b86","datavalue":{"value":"independence ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898730$D49F2046-0A49-4E51-A1C5-2F0FE23A55B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898730$73CB5EFB-3236-4C03-914F-FBDC71183314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898730$4091A9B2-5200-479B-B7B8-972C2E3C24C2","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":"Q1898730$7859EA96-FF26-44E5-AF12-2305FE486C46","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"598db56856f5cd106c8b005d75e1e8e933b79a61","datavalue":{"value":"https://doi.org/10.1006/jctb.1995.1043","type":"string"},"datatype":"url"},"type":"statement","id":"Q1898730$5B6DB1C7-0DE7-4212-9313-49603ADD4814","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"462026980782d56480fa4e59b739112ab605c0bb","datavalue":{"value":"W2065134396","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898730$9365071E-5BF5-454B-80C0-B45C2DD1E017","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"876a299fa594fe92582570566df54489e5046735","datavalue":{"value":"10.1006/JCTB.1995.1043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898730$C3769AE1-7C12-4294-A6EC-3C40436C0E69","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77ce49a3063d6a8064080eb4b93cf1fa7dba8799","datavalue":{"value":{"entity-type":"item","numeric-id":5126758,"id":"Q5126758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c03d821b346a5d108384fd3a3fd32b8a70d47cee","datavalue":{"value":{"amount":"+0.8730639","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":"Q1898730$E5DA83BB-BF45-436E-83B0-1AAD49BE7402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1eeda6d07ecadf86dd8e5d391272d08360362209","datavalue":{"value":{"entity-type":"item","numeric-id":2921419,"id":"Q2921419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fae1859e5d247442655badaf7a7d976ab48facc","datavalue":{"value":{"amount":"+0.8705507","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":"Q1898730$58D6A401-E7B5-48FF-82ED-A3290C8F649A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b235ed490adb565810efbcbb599e2c50bd664239","datavalue":{"value":{"entity-type":"item","numeric-id":5270410,"id":"Q5270410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fae1859e5d247442655badaf7a7d976ab48facc","datavalue":{"value":{"amount":"+0.8705507","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":"Q1898730$934B0B4B-798F-48B6-992D-9F2DFC4C984B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3476bc0ad72d1fcfe0d7bac686b4b2ea7b7c6aab","datavalue":{"value":{"entity-type":"item","numeric-id":4717575,"id":"Q4717575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85d210d143fc8e501c9bc9ed5783e2e68794936a","datavalue":{"value":{"amount":"+0.86995673","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":"Q1898730$7ABED6CD-FC5D-423C-9CD9-A42F84B7086D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68feda83064b9235d6297e7b7584b44ca3aa431e","datavalue":{"value":{"entity-type":"item","numeric-id":5317564,"id":"Q5317564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8732c92d9b434b4c3bdb1890293e9e5ea6a7a6ec","datavalue":{"value":{"amount":"+0.8687088","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":"Q1898730$9F868A41-4431-4BF3-BADF-68A236967976","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9940cf82cb7cabc82f362b2089b8009259319a22","datavalue":{"value":{"entity-type":"item","numeric-id":726518,"id":"Q726518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b5f0d920e8910693f1b8ae2a31d5df853211992","datavalue":{"value":{"amount":"+0.86616826","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":"Q1898730$1D13E0D5-3F13-41AC-8756-68D2A96E38C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ccea84b5970576130b1145beab7d66e8b49595d","datavalue":{"value":{"entity-type":"item","numeric-id":976086,"id":"Q976086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66e11a0d16f0a2a61d31a921bc0bf166fb22d378","datavalue":{"value":{"amount":"+0.8626827","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":"Q1898730$9F08995C-9F3B-4DA2-97DD-9B2BB4B5EBF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac920ff984a64db6daf424bdc303343e9cd24737","datavalue":{"value":{"entity-type":"item","numeric-id":1690246,"id":"Q1690246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f9a3cf4ecf434582892c4cabb65bc8b1d5e72ca","datavalue":{"value":{"amount":"+0.86221355","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":"Q1898730$9E5C9448-9A72-45D9-95CC-6E8EDC4C06ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8eb7d73a326967f810ad050468c2983df8629207","datavalue":{"value":{"entity-type":"item","numeric-id":2384807,"id":"Q2384807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa7ea53cd5ac6c5e75808b2ba748601fc7ae4daf","datavalue":{"value":{"amount":"+0.8613077","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":"Q1898730$8E4D7E15-1F7A-48C1-8390-4464A0D5FA74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb5578ce28a9e8952157080712af8ecf146db18d","datavalue":{"value":{"entity-type":"item","numeric-id":1292823,"id":"Q1292823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e125e00a8cb7df8fc63e1da4e321866cf5e76e1","datavalue":{"value":{"amount":"+0.8608104","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":"Q1898730$D2DA2C3F-F8FC-427C-BFD9-AE2AF183E4D0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/11/30_(Finding_large_independent_sets_in_connected_triangle-free_3-_regular_graphs)"}}}}}