{"entities":{"Q1386480":{"pageid":1397220,"ns":120,"title":"Item:Q1386480","lastrevid":68835429,"modified":"2026-04-13T02:23:33Z","type":"item","id":"Q1386480","labels":{"en":{"language":"en","value":"Finding independent sets in \\(K_4\\)-free 4-regular connected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1154637"}},"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":"Q1386480$E5E1995C-C637-4704-9D9F-3F7BD9C7D6D9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6554ab96ef898da7d2689e523fbd52aecaa01a75","datavalue":{"value":{"text":"Finding independent sets in \\(K_4\\)-free 4-regular connected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1386480$C513F189-42B7-420B-99A9-3748D9F05EBE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"93c2c0a20047264e4fc42689b7d78bfef86325fb","datavalue":{"value":"0896.05031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386480$FC45E7EA-170D-456F-B542-B7C5A4EDD836","rank":"normal"}],"P16":[{"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":"Q1386480$8EE0DB88-7872-4983-8D06-00A1FC2E4C57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc87f2effeae15ebb5545b248f363e7ddf15ef0c","datavalue":{"value":{"entity-type":"item","numeric-id":1386479,"id":"Q1386479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$0CF87D67-66E6-46B2-A50F-8CC2615B957B","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":"Q1386480$FF341031-7C51-439F-A087-D8BB9924DB78","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"55fb3f14c91fe25aa34a1cf0fe957b7dd1b3bb52","datavalue":{"value":{"time":"+1998-05-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1386480$60B69365-7705-4118-AA40-B73B11160911","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dbab53a7b2a3fef83d33bf28c6069ca3868e71f9","datavalue":{"value":"Let \\(G\\) be a \\(K_4\\)-free 4-regular connected graph with \\(v\\) vertices. Then \\(G\\) contains an independent set of vertices of cardinality at least \\((7v- 4)/26\\). Furthermore, the proof will yield a polynomial-time algorithm which will return an independent set of cardinality at least \\((7v- 4)/26\\) for any such graph. A family of \\(K_4\\)-free 4-regular connected graphs with maximum independent set of cardinality \\({3\\over 11} v\\) is provided, so that the asymptotically sharp lower bound lies between \\({7\\over 26}\\) and \\({3\\over 11}\\). We also provide a slight improvement over the best previously known result for triangle-free 5-regular graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386480$9B0E3BB2-AC6E-45AE-A3B3-462BF0ED97A7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386480$7AE7F5D9-1833-44D9-98B5-72E38BB4DC1C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b53f73690f0bbddda0afcf7f9946fdeae567e589","datavalue":{"value":"1154637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386480$30DC3163-F276-4817-85CA-8131480852EA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53174e500871c11571b526d3264b53153b21579c","datavalue":{"value":"\\(K_4\\)-free 4-regular connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386480$D6825B0C-F918-47EF-A363-D6FB611D1B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386480$F1E6765B-16B6-44F5-AF3E-2408D6B6B5B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386480$6B98E9C3-4644-43C8-AACF-FE26F4803569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a5025a1a769c82b75cc9ca009c016c469ef360b","datavalue":{"value":"triangle-free 5-regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386480$2E7CB284-B8F9-4306-B165-4F95D2085B23","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":"Q1386480$13002DF8-9E9C-4EDD-BB24-4F502613B56F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4a562570244178694ccf043fd096bfb4535ef2b4","datavalue":{"value":"https://doi.org/10.1006/jctb.1997.1772","type":"string"},"datatype":"url"},"type":"statement","id":"Q1386480$E7F9D2FB-7EFE-4A9D-95B9-7AB3FE0A32FC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e24752048e852ffcc248ce2f8b9ffae7cb6d45e6","datavalue":{"value":"W2081512224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386480$8B0C3072-EBD9-4E4E-BEA4-08EBE7099F2D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b41da683081378fbdb7a6cde8e39f82c87277d9a","datavalue":{"value":{"entity-type":"item","numeric-id":4111622,"id":"Q4111622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$9D458354-48BC-4D99-9929-3DDB00F5796B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c6708af21c3c7226ba8ca546cbdf76783683e91","datavalue":{"value":{"entity-type":"item","numeric-id":1377864,"id":"Q1377864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$9EB8A0E2-58F9-47EA-B51D-612673D31532","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":"Q1386480$676CCC02-54FF-4C74-AD70-CC7EE2F32280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$78088228-FD62-4EF0-8E1D-A7C64F88A6FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67085864f6a7b39588c06ae975acc511fd0f7ad6","datavalue":{"value":{"entity-type":"item","numeric-id":3872499,"id":"Q3872499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$3E2A00F1-EDE2-4C98-A960-9A0D252EFFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"692b548ccbd94a49cafe20bf12dda5ab9c361611","datavalue":{"value":{"entity-type":"item","numeric-id":3863917,"id":"Q3863917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$DFE1F96A-7149-48A6-8021-25D91CDF9B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a81b4aaba98fb47fede350d1de7c54f1f7d1e85","datavalue":{"value":{"entity-type":"item","numeric-id":4712120,"id":"Q4712120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$9E5D989B-9E88-40EE-8A30-C1AC80346AE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eddc8fb0d36c3ad45444830f80fe5afd4c7cb55f","datavalue":{"value":{"entity-type":"item","numeric-id":1898730,"id":"Q1898730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$155AB57D-49A3-4313-8577-3ADE6D564E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"065caf573ea220073d501a061cc63f7f866dd2ca","datavalue":{"value":{"entity-type":"item","numeric-id":4717575,"id":"Q4717575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$9AC350FF-D920-4B9F-9636-17343C4FB4DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2ecc9d4f1b6e65f0dd6a77c7093b2bfd51dc61","datavalue":{"value":{"entity-type":"item","numeric-id":798679,"id":"Q798679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$21AA8203-E74A-4384-A5B9-D7196BAFB290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b89c6a980d117288eef80f3b9c173c3ac3c9ac81","datavalue":{"value":{"entity-type":"item","numeric-id":1917491,"id":"Q1917491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$6788C504-1A5D-4E1F-80A6-395EF6983B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b267b1d73cf3767c6f07e1a29a91d505440fe717","datavalue":{"value":{"entity-type":"item","numeric-id":3981345,"id":"Q3981345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$B3986506-5829-4122-8D16-0893A3ED6160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8b9734cc4e3873747e7237cf9f86a64fdecead","datavalue":{"value":{"entity-type":"item","numeric-id":3745878,"id":"Q3745878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$5030AC7C-2C01-4332-9D1E-FB16D3CF4130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa0e14bfd589a9ae5b8bb6ac61a529ec2f667fcb","datavalue":{"value":{"entity-type":"item","numeric-id":3864546,"id":"Q3864546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386480$4CED434E-179F-4232-A9F2-F3ED8883AE46","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"af2686f29ade1985302106663447380715a03644","datavalue":{"value":"10.1006/JCTB.1997.1772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386480$BB39C42F-DA52-4E31-9EC8-78CEC8BC212A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f693e599ad15070293e54a162dd9802b6bac4a0","datavalue":{"value":{"entity-type":"item","numeric-id":1949035,"id":"Q1949035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42109d3ee55f8adf7b23efb230a29e0d9371fe29","datavalue":{"value":{"amount":"+0.8602808117866516","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":"Q1386480$CD7D35A2-D6B3-4626-BBFC-D65331056658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1f7321e0963bd9bae7eef133cdd578ca3c8e261","datavalue":{"value":{"entity-type":"item","numeric-id":400359,"id":"Q400359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e29c97d7e9aead191b12ac7f651e99923c42d6e","datavalue":{"value":{"amount":"+0.8518585562705994","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":"Q1386480$CBB9C8FB-DA43-420A-BF74-FB9248D6CA55","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":"bcacb19c8e3a80e9b76442b1998ddc77397ac295","datavalue":{"value":{"amount":"+0.818156898021698","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":"Q1386480$4BC097CC-1888-4E09-9CD9-8223089BCA8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce0055bcbc8ddcc5c38f01df7a8aa3830995f546","datavalue":{"value":{"entity-type":"item","numeric-id":1898730,"id":"Q1898730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34cef426957c97f3c7ef282c05109fcfb8f53f60","datavalue":{"value":{"amount":"+0.8117274045944214","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":"Q1386480$47EA1E75-8861-4EBA-A083-0D59CDE25120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2047fa147ad0f4ca07fb6b75a66374e4e8477df2","datavalue":{"value":{"entity-type":"item","numeric-id":998471,"id":"Q998471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d39259fb1900918cb5aa1a0595af2767f52514c","datavalue":{"value":{"amount":"+0.8076097965240479","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":"Q1386480$3F50FBE3-A87F-47A6-9776-16EA2D2ADFF9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding independent sets in \\(K 4\\)-free 4-regular connected graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_independent_sets_in_%5C(K_4%5C)-free_4-regular_connected_graphs"}}}}}