{"entities":{"Q1084418":{"pageid":1095170,"ns":120,"title":"Item:Q1084418","lastrevid":66105147,"modified":"2026-04-12T07:35:21Z","type":"item","id":"Q1084418","labels":{"en":{"language":"en","value":"About recognizing (\\(\\alpha\\) ,\\(\\beta\\) ) classes of polar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3979116"}},"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":"Q1084418$9093D2A6-85E1-4416-860B-362B3943A1A2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6aae0bd8b741fd1a4e1171962cfef1df4cba66db","datavalue":{"value":{"text":"About recognizing (\\(\\alpha\\) ,\\(\\beta\\) ) classes of polar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084418$C4B4AD18-2902-4133-B3E6-DB51AE9BFC55","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cbf94c8b9e3bc32401ca519e1d226b004be151ae","datavalue":{"value":"0606.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084418$5D78797B-B684-4736-A033-F8D8DEA81156","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"130822fcb90d038b7af72d1b8c2eaf88dd1cc397","datavalue":{"value":"10.1016/0012-365X(86)90113-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084418$78465E03-235C-4F47-BA44-3E67FB93DE19","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ba06175f37b98d67e3f2d14dc10963f7f97d59a","datavalue":{"value":{"entity-type":"item","numeric-id":678858,"id":"Q678858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$40B84D74-7B69-4998-8602-5B3A951F9EB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7eab1cde51174074dafafa36609484b737f2c6df","datavalue":{"value":{"entity-type":"item","numeric-id":1176733,"id":"Q1176733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$57602E15-2F7E-4D5B-BBB6-4EDD1B4E1F59","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$EFAC8183-F706-42A6-8273-8166959AD53A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1084418$87C73ABA-6957-429D-8567-9A495949E3A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0842fb1adcc13a3579e1c9e4d254f42c2984e633","datavalue":{"value":"The paper concerns the concept of a polar graph (other than that of F. Z\u00edtek). A polar graph is an ordered triple (G,A,B), where G is a graph and A, B are disjoint sets whose union is the vertex set of G and which have the property that B induces a subgraph of G, all of whose connected components are complete graphs, and A induces such a subgraph of the complement \\(\\bar G\\) of G.    Let each of the symbols \\(\\alpha\\), \\(\\beta\\) denote a positive integer or \\(\\infty\\). If none of the connected components of the subgraph of \\(\\bar G\\) induced by A has more than \\(\\alpha\\) vertices and none of the connected components of the subgraph of G induced by B has more than \\(\\beta\\) vertices, then it is written (G,A,B)\\(\\in (\\alpha,\\beta).\\)    The problem of recognizing whether a given polar graph (G,A,B) belongs to (\\(\\infty,\\beta)\\) is called the POLAR(\\(\\beta)\\) problem; the analogous problem for (\\(\\infty,\\infty)\\) is called the POLAR problem. It is proved that POLAR(\\(\\beta)\\) for all \\(\\beta >1\\) and POLAR are both NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084418$4C32716E-E7CF-459E-86DF-728F6DBA1F5E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084418$AF0209C9-6645-4954-AB09-9332D53DAC5A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"93218d94e79814f1ddd41895edc4130dc6f38526","datavalue":{"value":"3979116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084418$AF053889-81FA-40A4-93BB-6D30B10E2EF8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50dc5a1d041f9e444212e60e5236dde69d229f7d","datavalue":{"value":"NP-complete problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084418$305931AE-02B0-4D7C-85BE-4A4C85D978C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a2f39e0f0ef9d3bcdcd9fa3112017542fd63a71","datavalue":{"value":"polar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084418$90FEC29C-A319-4F02-9D5E-5718C8036176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3da151c97381362f5897c1d6a4aeb9de066762c","datavalue":{"value":"POLAR problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084418$27858668-DE8B-4FAA-B010-71AF5021010E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$39BACE66-843A-4A36-9ECD-FF592EAE49DF","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":"Q1084418$28042564-0E1D-474F-B8A3-799853E03458","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2612448b9f543e587e3ebb6cbfa231ea42870605","datavalue":{"value":{"entity-type":"item","numeric-id":4154894,"id":"Q4154894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$50B6E129-E214-4AA2-8A19-BB9648ABE5E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f3be34444b87e94060eeddaad78e0c69a90fd2","datavalue":{"value":{"entity-type":"item","numeric-id":4165164,"id":"Q4165164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$F4BE0BDA-E0A5-483B-BAB7-D1AAB9A2B473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8add4627ebed45e331231c9fcb96d24b9b77ef2d","datavalue":{"value":{"entity-type":"item","numeric-id":4193514,"id":"Q4193514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$43921FA2-269B-46E9-970D-EDB358E1F260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$746F28A1-65E4-472B-B272-03DD381075DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41cc6a286064615a5226bdd0939f0f85a946c13e","datavalue":{"value":{"entity-type":"item","numeric-id":1167741,"id":"Q1167741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$EFEE3A25-7328-4993-AB28-78C7D8B46A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bec8ebb9492526684739e0d9b557be0cf67a410a","datavalue":{"value":{"entity-type":"item","numeric-id":3728949,"id":"Q3728949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$807627EF-0BF3-4290-99AE-8C50F675750D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6619826e480ae1ba64e56a53850ec42b5b121be9","datavalue":{"value":{"entity-type":"item","numeric-id":3743346,"id":"Q3743346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084418$B9E81FC4-7D57-4F9D-AB2B-53392FBD7A5E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"959db87f337441f5ac32bf6aef39247b0836e222","datavalue":{"value":"https://doi.org/10.1016/0012-365x(86)90113-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1084418$C991CF9C-24F5-44BD-8994-73BAC3EC9DBC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"adfae6cb952cc833f95c8c15de58a8fe0195d8ec","datavalue":{"value":"W192680164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084418$20A40918-120B-4033-827F-579718FB47CE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41ebd3a21447fdf7f70da228a82332ca015cd0f9","datavalue":{"value":{"entity-type":"item","numeric-id":3734451,"id":"Q3734451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b9468dd3987e0b615912edc95983b538173c774","datavalue":{"value":{"amount":"+0.9119218587875366","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":"Q1084418$873AB3A2-0946-4246-A8AB-FB767F1FDA16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c13f70201d475af65b3cde1257b4ca2b0c75a261","datavalue":{"value":{"entity-type":"item","numeric-id":5899394,"id":"Q5899394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7feaf5c866d1238b218eea4e0ece955a724d75e","datavalue":{"value":{"amount":"+0.872234582901001","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":"Q1084418$87E674E1-4A50-4A47-AB8C-5FC5BBA15E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e62c08fa8adac5f9d96f5a7efa59ce32fec626d0","datavalue":{"value":{"entity-type":"item","numeric-id":4691790,"id":"Q4691790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97c1c518b8f9cfe76d7b006d7ab5596769c06ae4","datavalue":{"value":{"amount":"+0.8668654561042786","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":"Q1084418$D72A0704-7298-4E63-A86E-AE41FE935D32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbb13f768fe231a84dca06f51a20f09daed2f3a8","datavalue":{"value":{"entity-type":"item","numeric-id":3743346,"id":"Q3743346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f94f3af3684bac6162709b65c3071037523e506e","datavalue":{"value":{"amount":"+0.8593822717666626","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":"Q1084418$46605751-C088-4537-8AA1-2EEC3134FBBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7a28a35597c61a92f90bfb2c33043f47bdf53f9","datavalue":{"value":{"entity-type":"item","numeric-id":5900347,"id":"Q5900347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"621601f0931ba9f1af95406cfb21c4384e1cecab","datavalue":{"value":{"amount":"+0.8535556197166443","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":"Q1084418$E557B1A2-3F20-4C01-AFA7-41472F92EEBF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"About recognizing (\\(\\alpha\\) ,\\(\\beta\\) ) classes of polar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/About_recognizing_(%5C(%5Calpha%5C)_,%5C(%5Cbeta%5C)_)_classes_of_polar_graphs"}}}}}