{"entities":{"Q686246":{"pageid":688095,"ns":120,"title":"Item:Q686246","lastrevid":63608652,"modified":"2026-04-11T14:19:38Z","type":"item","id":"Q686246","labels":{"en":{"language":"en","value":"Independence and domination in polygon graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428103"}},"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":"Q686246$53EBBE6A-B17B-4BB1-9F2E-BD12A8BE52B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"40555d1aa67c3c32dfcda9e4c5c7f786bdff8359","datavalue":{"value":{"text":"Independence and domination in polygon graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686246$F522B2BB-E26E-4BD1-9E2A-0AE83E21CB23","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c0bb6248d510ff480920cfca3922ef3856eae445","datavalue":{"value":"0785.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686246$006FEC64-931B-4BA2-A3D6-41D365681671","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"356996e5683d805b0533cc03cdfb556c8468ed62","datavalue":{"value":"10.1016/0166-218X(93)90222-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686246$3B74697A-ECCB-4FE6-8D73-377FC578D70F","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":"Q686246$2C585969-BBCA-475B-B2FE-FBBFF4C7E956","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a56fa44f05f9c865c2049cda281119f7946a004","datavalue":{"value":{"time":"+1993-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686246$E4398EF8-7497-416B-B1FC-FE329465DEA2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4d578c2bcf240c66bb4bec8e8fad3610bf834a05","datavalue":{"value":"Polygon graphs are the intersection graphs of chords inside a convex \\(k\\)- polygon for some integer \\(k\\). This class of graphs generalizes permutation graphs and is a subclass of circle graphs. The problems maximum \\(r\\)-colorable subgraph and minimum dominating set are known to be \\(NP\\)-complete on circle graphs. The main results of this paper are polynomial time algorithms for these problems on \\(k\\)-polygon graphs with fixed \\(k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q686246$802AD838-9AAA-42D9-A6A2-3EF214589E52","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5af1aa80224172db75f7ae535f0d2940793ea880","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686246$F571F663-F0A7-4D4B-B63F-C46A3D00893A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686246$482CD33C-89C3-48B3-A0AE-7A80EE234C6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686246$C29CDB6B-AF1B-4C95-85A3-9AB249026898","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3471a1328788acd620ec922d41e4cb8e258b3a30","datavalue":{"value":"428103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686246$E2848BD5-45C3-4DEF-BBE8-4B8A8BFC73DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"041c2dcef8ec4dcdad37697d2b1202c64e1ae562","datavalue":{"value":"polygon graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q686246$F20D9DFF-1C6B-4A94-ABC1-5B5B5D921695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f0c7fa4330fc969e60a8673977bb1e27a2fe7c1","datavalue":{"value":"maximum \\(r\\)-colorable subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q686246$A983520F-8D09-42CF-841A-F07B0749790A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0a05fe9852c745ffafd3f04bb0e8e8bc9f47221","datavalue":{"value":"minimum dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q686246$FA10650A-298B-45A8-8185-A862CDFC6AB9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"087177969742b876ace983fe9dc71a9079719999","datavalue":{"value":{"entity-type":"item","numeric-id":916680,"id":"Q916680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686246$70E0351D-AFD5-49EE-B3E1-E6EF06A6A1F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8fb2b37962e8c2e7db338cb8271d20e81b4c70da","datavalue":{"value":{"entity-type":"item","numeric-id":1060965,"id":"Q1060965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686246$D3F5B3B3-3662-4EE1-A1BC-AB8E99A7AD03","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":"Q686246$74910D27-4852-4B53-AEDB-5C0E564174FD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"74932f79c2ba549ae58af939161b35db92eb95c2","datavalue":{"value":{"entity-type":"item","numeric-id":3694712,"id":"Q3694712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686246$5B98803D-D573-4516-9F08-BE691AD64075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1901aedd2d8549517a3f77a27b2a3787fa019529","datavalue":{"value":{"entity-type":"item","numeric-id":3731637,"id":"Q3731637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686246$E1E596CD-60BF-4025-8843-A3621BCAB53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1e2e6abdbb3a464ba621eca18bcd8f91d2af79f","datavalue":{"value":{"entity-type":"item","numeric-id":4710682,"id":"Q4710682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686246$DCD174B1-6DB4-4CF2-B697-07C67C0671FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8966655ecbb1863d7d15b1de7a7a366acdd2bc41","datavalue":{"value":{"entity-type":"item","numeric-id":3964622,"id":"Q3964622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686246$39671BA2-CA23-420F-9AE4-346BFB90FB00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"329a5de00a7f842ca79da38a1dc02d38dfdd7fbb","datavalue":{"value":{"entity-type":"item","numeric-id":5675749,"id":"Q5675749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686246$D1917742-6D93-4440-8E33-30956D3C4D2F","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":"Q686246$2273E539-D620-44E1-A7BE-5B65B2A32DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef59647203c58ee1f83043f928eba109372c62e9","datavalue":{"value":{"entity-type":"item","numeric-id":1209148,"id":"Q1209148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686246$32815AE3-30A8-4898-ABDB-3FEF617EFBB2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0151a8b705b7e705c61295535f65e11bc36dc08a","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90222-a","type":"string"},"datatype":"url"},"type":"statement","id":"Q686246$911633B0-5099-491B-A96A-5C120E176359","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c4176c1346c49cb3fab3cd726cfcb17a70e11937","datavalue":{"value":"W1971604681","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686246$33D896B9-4C6B-45B4-9C48-D83DCDF3A878","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e66b8a07e90aa589a138c14640eccc76e0f27365","datavalue":{"value":{"entity-type":"item","numeric-id":5284020,"id":"Q5284020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e293b0f8fbe62c9b62b83a3655c7cb401398cc0","datavalue":{"value":{"amount":"+0.9147374033927916","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":"Q686246$CCF76C46-2437-45E4-9CCA-E33351DB176B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae57f450e1d0cbf25ca93766f691a5078abcf6da","datavalue":{"value":{"entity-type":"item","numeric-id":4377123,"id":"Q4377123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dab27c10a7aaf7fb3e00c87c699d63d1ffbe49af","datavalue":{"value":{"amount":"+0.8636793494224548","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":"Q686246$6D740A4C-8B54-49E2-8465-2706EDB8AAB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6a10675bf57dfa487683644600d75e13c8c2057","datavalue":{"value":{"entity-type":"item","numeric-id":1209148,"id":"Q1209148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf396740529c825418ab2418b779eeaf1fc31961","datavalue":{"value":{"amount":"+0.8190560936927795","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":"Q686246$10D6962B-3E2D-4D33-987B-7A00EADEF7DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cf4be84a04f697e305c73c6efd5e03c37050e80","datavalue":{"value":{"entity-type":"item","numeric-id":4517186,"id":"Q4517186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cd3afb6836ee07f876f0766e7ba3b95466694af","datavalue":{"value":{"amount":"+0.8186268210411072","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":"Q686246$9E420894-9DBD-4340-9814-B7FB94B53AC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efa930f1ed6f9b8f5a7611e0af403680cc566ac1","datavalue":{"value":{"entity-type":"item","numeric-id":5193167,"id":"Q5193167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a0cf0d266ffe8c589b236a048fbe7985959c0a9","datavalue":{"value":{"amount":"+0.8088522553443909","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":"Q686246$BA4A09D9-8127-4EC5-8A14-424AF1CCAC41","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Independence and domination in polygon graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Independence_and_domination_in_polygon_graphs"}}}}}