{"entities":{"Q1825646":{"pageid":1836388,"ns":120,"title":"Item:Q1825646","lastrevid":73461630,"modified":"2026-04-14T16:05:18Z","type":"item","id":"Q1825646","labels":{"en":{"language":"en","value":"Achromatic number is NP-complete for cographs and interval graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4121423"}},"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":"Q1825646$394622C8-956B-482E-9E33-0BA414744C42","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cf8d27d86d818a01235210819d08459056a442a7","datavalue":{"value":{"text":"Achromatic number is NP-complete for cographs and interval graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1825646$202D9DB2-EDBF-4780-8FF3-CE8CFFA2B5EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b6406b7bcc7cf194f1a09d2985a90a5ab6a49892","datavalue":{"value":"0684.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825646$D962B957-5DF6-4C4A-8636-C32AEE969A8F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c9a3bb0ef6e86063f530900947bca09f503a77fa","datavalue":{"value":"10.1016/0020-0190(89)90221-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825646$9A27722F-B5E5-4A7D-B20E-5A47F687EE0E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$370F6412-79FA-4B80-88E1-256B906A669A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1825646$ED548BE3-95EF-45FC-B06B-35843B3104F2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"60745ae948afea44aeb23138fdbb87b5da64fa69","datavalue":{"value":"https://dspace.library.uu.nl/handle/1874/16576","type":"string"},"datatype":"url"},"type":"statement","id":"Q1825646$BAB75280-8DD1-437C-B8BE-E3DB05916161","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825646$C50D59BB-C1B8-4024-8BA5-D383CA22CCD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825646$92F1B47D-7FC8-4AB6-AA8A-E70F39235DF4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ccb84466ba43c8345d2b90b32ff86a8dbe588a25","datavalue":{"value":"4121423","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825646$9A942DFB-F0BB-4ECA-9507-A538E216418C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df7fe14c7b38fce52b1c24ba095651ec0120be54","datavalue":{"value":"cographs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825646$0312119D-AEB3-4579-BECF-1F82BDE73C7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d59ab2c83e0dbd443ebc1f3d0412b712509c0917","datavalue":{"value":"interval graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825646$C125E227-EA2A-4A04-9A6F-B7BA9923D18A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825646$27F04E4A-CD39-4A08-B22E-940708E2D5D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"926e613762971a9014a8b1ed071772bdcf0a0812","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$EEC1146F-14BD-415A-B309-74535E2F7A77","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":"Q1825646$AC6D6C94-6B7E-4CD6-91C9-0F8D1051452C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e5412522d120f72ae55b08705abdc7aec10ef4a9","datavalue":{"value":"W2160875590","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825646$6CE26AB1-1383-455C-B8E7-934F4FB85C95","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"189b4fc3c77d1e614cf4e0621c1aa1a9ecc6c885","datavalue":{"value":"Q56390758","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825646$76AD9B2F-10A7-4E68-8C9A-BD7633C6E345","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc69c6156e9471fec17a5d754a7b363dbf0153f6","datavalue":{"value":{"entity-type":"item","numeric-id":3812222,"id":"Q3812222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$00DF5127-9A43-48B7-9492-03D30F18B282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c6807bb69250e5f3aea352a72773fdcbd3a35f1","datavalue":{"value":{"entity-type":"item","numeric-id":5903263,"id":"Q5903263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$FA9CED6D-AB42-4153-A9E4-0BB93CCA471C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$DE094E6E-701B-4451-944B-EB4EFDD6CCDA","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":"Q1825646$90A235A1-1942-4C01-BF59-B136EAF9F099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c419329cf6a4ec59893cd2cee822bc47fc6dde6","datavalue":{"value":{"entity-type":"item","numeric-id":3910550,"id":"Q3910550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$1522B2FD-B092-446F-AC1F-6D7F9C4D22B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d22d1a66627507c9e175f0940657f78d850ce78c","datavalue":{"value":{"entity-type":"item","numeric-id":3956413,"id":"Q3956413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$EF3733DB-922B-43E2-8B50-FE55CAE53EA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$BB947430-36E8-478C-BBB1-E06C48E3E171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fddf78676d43f688f22d0ab9603f5b22b0a030","datavalue":{"value":{"entity-type":"item","numeric-id":1066674,"id":"Q1066674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$DABD3CCE-8B04-4D87-A480-1D5782D0168D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd6675c6fd35aca2112b944a189a93b533f77ae","datavalue":{"value":{"entity-type":"item","numeric-id":5903156,"id":"Q5903156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$286D42A9-BE8C-4872-9E11-01628E40F815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64b78af75acd34bb4040222305089370136cc963","datavalue":{"value":{"entity-type":"item","numeric-id":1090458,"id":"Q1090458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$036F45F4-8076-4635-9180-7427867C42A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"886ba032e540aea708d21bd27fbc92799a765ca4","datavalue":{"value":{"entity-type":"item","numeric-id":3686754,"id":"Q3686754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825646$BB287173-47B7-4BD3-AE7F-C9F71286810C","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"43f92bf90bd0c4f03b0bbf60e1932e17180c7915","datavalue":{"value":"journals/ipl/Bodlaender89","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825646$9F2D4968-C22D-417D-BF99-EE437446AB40","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"348bb9cc868a76453f77e6079e1dc111de670f19","datavalue":{"value":{"entity-type":"item","numeric-id":5897262,"id":"Q5897262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5629a965d3d7fb7eba89a4ccbb0f96e7a11beb2","datavalue":{"value":{"amount":"+0.88551944","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":"Q1825646$FA34E4D5-88FE-46A0-A624-A8E9D182E278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd8f9f5ba0bddfe5f9dfdd9943ae19ad4d20c1ae","datavalue":{"value":{"entity-type":"item","numeric-id":3126442,"id":"Q3126442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"284d9f909f24ae76f7b8e03185e6b13ac7c3c24a","datavalue":{"value":{"amount":"+0.88167334","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":"Q1825646$08F57877-0085-44C0-995E-FF004F5F344E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83042f3b6d5555590542a4feee712589c6d15dab","datavalue":{"value":{"entity-type":"item","numeric-id":3320413,"id":"Q3320413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2fc21915798b70fd42953ee82148d7aac248ff9","datavalue":{"value":{"amount":"+0.877021","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":"Q1825646$EDDE1CE8-35E4-4C4C-B06C-CF3776A34966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5476152cdafc596c701cf38586292c03d4739e75","datavalue":{"value":{"entity-type":"item","numeric-id":1065819,"id":"Q1065819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9079f308b688d7a65d4cf86bce7c3fa47a7ff1f6","datavalue":{"value":{"amount":"+0.8766688","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":"Q1825646$A1328CAA-A724-46FD-BD6B-9EE69CB5D728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4d98a3d77a64f1658b06257fda175d3d8d8292f","datavalue":{"value":{"entity-type":"item","numeric-id":3216676,"id":"Q3216676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9079f308b688d7a65d4cf86bce7c3fa47a7ff1f6","datavalue":{"value":{"amount":"+0.8766688","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":"Q1825646$CC085835-28F9-4966-B8DA-1E69161FFBF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99eafc748f8bf7f275cb2afc54df2ee5434d0511","datavalue":{"value":{"entity-type":"item","numeric-id":1117240,"id":"Q1117240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d445452fc60d8cab5441b4f2a94ebdbf650ca99","datavalue":{"value":{"amount":"+0.8715606","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":"Q1825646$4835A88B-F8BD-4592-AB01-3AFE99DF61DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3154f68fb43e3627d5f1685bfb7845940ede6d8","datavalue":{"value":{"entity-type":"item","numeric-id":4970154,"id":"Q4970154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb2673afbf4cadafc684867aa9941df60bfbcdd2","datavalue":{"value":{"amount":"+0.87152386","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":"Q1825646$E6518A59-7DC6-4684-8B9D-7888E7251C98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"017b593c564259eebcd07687e5e3f3517ec750c8","datavalue":{"value":{"entity-type":"item","numeric-id":2656326,"id":"Q2656326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6285e34c873fdb7e1ef425be172d757158a2c035","datavalue":{"value":{"amount":"+0.8711417","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":"Q1825646$ECE31566-7448-4DCF-A232-1C873F01E946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7605ac4553825f6edb3788d3ba70f97181d0083e","datavalue":{"value":{"entity-type":"item","numeric-id":3325761,"id":"Q3325761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea321b39faeabd97f6a950e1ecc56ba5cfb68cc6","datavalue":{"value":{"amount":"+0.8691122","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":"Q1825646$66E15D7A-5875-4DF4-A11A-D26835EAE961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e42833039501cafe238c250c5e627d53a38486b","datavalue":{"value":{"entity-type":"item","numeric-id":4498314,"id":"Q4498314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6198f49fae9ffdd6932d4d4b275eb40597223735","datavalue":{"value":{"amount":"+0.8690547","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":"Q1825646$2D82DF18-297E-4F17-B6CD-F89E8A9F1C32","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Achromatic number is NP-complete for cographs and interval graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Achromatic_number_is_NP-complete_for_cographs_and_interval_graphs"}}}}}