{"entities":{"Q1208469":{"pageid":1219218,"ns":120,"title":"Item:Q1208469","lastrevid":77960624,"modified":"2026-05-06T10:27:27Z","type":"item","id":"Q1208469","labels":{"en":{"language":"en","value":"Stability number of bull- and chair-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166467"}},"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":"Q1208469$79EC8A57-F89E-4AEA-A7A8-2640C11BF86C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ff1833b30acb58d1b28288920e09d18bf7bac3fb","datavalue":{"value":{"text":"Stability number of bull- and chair-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1208469$19F9925D-FBBD-446B-A2BB-E0F6C849A17E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"75fd9b5921a08647aa9bc4a332ca7c82fb54e2cf","datavalue":{"value":"0773.05070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208469$20BF3A5A-ECDF-48B2-968B-32C53EB51045","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4cf56643727493eeb510d3ebee322c258eb8f270","datavalue":{"value":"10.1016/0166-218X(93)90032-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208469$BE903C34-DCB0-4058-8F60-5C5C1386A328","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"04e71569b0ebdef8629fef55e83176d19ee5910a","datavalue":{"value":{"entity-type":"item","numeric-id":849136,"id":"Q849136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$5948928A-D54D-464C-A631-0F692252D014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3de34c40bbd436145163ee502934245d6246cef6","datavalue":{"value":{"entity-type":"item","numeric-id":173870,"id":"Q173870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$8D9320FD-F1B4-4A7A-8404-70933A273E0D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$C05C892B-267F-4F8D-A57B-57509F2AACD1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1208469$05705947-2F29-4396-9DDF-5CAE92B71395","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c53585a97867c267c115b169bbd87a985a9c33dc","datavalue":{"value":"The authors regard finite, undirected, loopless, and connected graphs. A stable set in a graph is set of vertices, no two of which are adjacent. The size of the largest stable set of \\(G\\) is called the stability number. A bull is a graph with vertices \\(a,b,c,d,e\\) and edges \\(ab,ac,bc,ad,be\\); and a chair is a graph with vertices \\(a,b,c,d,e\\) and edges \\(ab,bc,cd,be\\). The problem of finding a stable set of maximum size in a graph is NP-hard.   The authors define a class of graphs which is closed under taking induced subgraphs and contains imperfect graphs and graphs with induced claws. For these graphs the authors describe a polynomial time algorithm to find the stability number. This algorithm is a iterative procedure which, at each step, builds from a graph \\(G\\) a new graph \\(G'\\) which has fewer vertices and has the property that the stability number of \\(G'\\) is equal to stability number of \\(G\\) minus 1.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208469$58B5ACF0-9665-42B1-B2C1-16EB5A26CA4D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bee1f7445f48f88ea32c13733d6b7ad82b5d2674","datavalue":{"value":{"entity-type":"item","numeric-id":803176,"id":"Q803176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$0ACDE885-214E-478B-BD1C-C0123501A791","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208469$BBDC0DBA-3350-46D8-8BB1-C74AB7727FDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208469$3AA9DB35-99EA-440E-95B7-0A5A27434CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208469$BC1877A1-F1B4-469D-B187-175CE6174D85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208469$81C28AA7-7EAC-4BC0-8E4A-6AAAC7DA4415","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"60e83724e66cbe9e2a509acf0ac0e049c5b768f8","datavalue":{"value":"166467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208469$A87DDAA4-91C7-425C-9285-7873EBDE999E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87e0e2197df31604dd9f16334c9c805616d74d2d","datavalue":{"value":"stability number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208469$EB565BE8-2421-4711-8CA5-DABF7DA5203F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbabd615306bd49f8fab2a684552f54455258f63","datavalue":{"value":"bull","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208469$097D1F5E-F9AC-4F1A-B8B4-612F36B6B108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03085a9ea63c13ca51766e21e0c9407a1b71184b","datavalue":{"value":"chair","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208469$0C65D97B-262F-4CAF-91BB-A6E6F92C37CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208469$D6A8A3ED-6AA2-49FC-87FC-94621AC9CACE","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":"Q1208469$28EA0AF1-604B-4DE2-AB37-BAD768F46EEE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$5659A7C6-BF5F-41F7-B035-D319904643A0","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":"Q1208469$B605C679-633E-4EE0-A862-1D2F5DE24BB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54f80bd66875089f385bc846e7e7f8ca82fdf2a5","datavalue":{"value":{"entity-type":"item","numeric-id":1095938,"id":"Q1095938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$AA6E76D1-47D0-4CA2-BDDE-6CDB0F19FCBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6158b50eeb07f11af0caa758cb3e8ea0fab5c43e","datavalue":{"value":{"entity-type":"item","numeric-id":2366214,"id":"Q2366214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$BA2A7B31-8578-4F00-AC1F-AE2CCEFAE26F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$E96A42B2-8EF6-4900-A071-493B59F1A05A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$43AA21EB-FDFA-4173-8E36-B326BBF29E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"974ebda8b7969127d2e6a9dc9704cb8e040cc76f","datavalue":{"value":{"entity-type":"item","numeric-id":1068855,"id":"Q1068855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$C7334B84-9FF9-44FE-A608-EE73144CD3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4c570bda964b76e5755c02e78b4470318c201fd","datavalue":{"value":{"entity-type":"item","numeric-id":1080863,"id":"Q1080863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$4602AA85-7A0E-4130-82AA-9835EB77C309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4430547256196434a5fcb8ecc7f9eb44d98ed973","datavalue":{"value":{"entity-type":"item","numeric-id":3899836,"id":"Q3899836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$662D0694-A9E9-4EC6-8469-99560CE0C20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$159B34CD-4059-4C65-89C8-C260A4C8FCE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ada71f343b2168554ef3d8e68058bb18dbed1fd2","datavalue":{"value":{"entity-type":"item","numeric-id":1139605,"id":"Q1139605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$1A9D741A-E970-42BF-9F9C-2FACBF32F8B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f98527e95e30b0522da5b0d1ff72ede7cfbae1f8","datavalue":{"value":{"entity-type":"item","numeric-id":1144589,"id":"Q1144589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208469$671B99BB-37EF-4443-BA87-29EC192A9B6A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"918d6f0cf0e14528c97882fa9c2ad90e2fa9bc0a","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90032-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q1208469$E9478906-7B13-4BF5-BAD6-7315298F2455","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4ce4953fb8aeabee090a2a386a3aff27339208fc","datavalue":{"value":"W2044614108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208469$E2BBBF15-E3E7-40BF-97EF-9777D0208123","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7043120e2c48838812bd3549fac85137264fb531","datavalue":{"value":{"entity-type":"item","numeric-id":1408811,"id":"Q1408811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f65a8817cab1a0909d577a69fef677be4dd4abc","datavalue":{"value":{"amount":"+0.8783786296844482","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":"Q1208469$3EEA5C86-BC85-4350-9396-AE639FC1BF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99460681fc0475db79093303c54bbcce716a7ec7","datavalue":{"value":{"entity-type":"item","numeric-id":1029074,"id":"Q1029074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f65a8817cab1a0909d577a69fef677be4dd4abc","datavalue":{"value":{"amount":"+0.8783786296844482","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":"Q1208469$C2FD42B9-5B18-4EF5-A83F-50B8786D665A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"724055e01bf179cbf0eed78cb81a5aa816f1644d","datavalue":{"value":{"entity-type":"item","numeric-id":4211743,"id":"Q4211743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79ac477112c6244c66955ed8331b2b16afdfe079","datavalue":{"value":{"amount":"+0.8385300040245056","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":"Q1208469$C6422838-4C80-45E3-819F-CA47443DE790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"836d4949d5bfd7f343a57c1d924047daebed4d28","datavalue":{"value":{"entity-type":"item","numeric-id":3181049,"id":"Q3181049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7ef69ff5f5a872c5d184fbf9b2ab49e80e70e3c","datavalue":{"value":{"amount":"+0.8047497272491455","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":"Q1208469$03EA06BF-5B61-44DD-9E65-37E5902AFAFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc82714269b19a8c000525c28886a4e5559fdd54","datavalue":{"value":{"entity-type":"item","numeric-id":1709548,"id":"Q1709548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f81d151cb6bc60eb72bd5359451f358aa7cd0362","datavalue":{"value":{"amount":"+0.8037683963775635","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":"Q1208469$2DEDFAC2-76D2-4397-89E5-AEC5FE122519","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Stability number of bull- and chair-free graphs","badges":[]}}}}}