{"entities":{"Q3557504":{"pageid":5587408,"ns":120,"title":"Item:Q3557504","lastrevid":49560526,"modified":"2026-01-07T19:38:19Z","type":"item","id":"Q3557504","labels":{"en":{"language":"en","value":"Deciding Relaxed Two-Colourability: A Hardness Jump"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5700320"}},"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":"Q3557504$3E2E14CE-986C-4FE8-9A33-9A3AE2A24A49","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"044e0fd8c7bd8a02f12b76a8a2ee66cb383205a6","datavalue":{"value":{"text":"Deciding Relaxed Two-Colourability: A Hardness Jump","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3557504$D10D042B-C3E7-45F7-8918-0CD6F6F33209","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e96a16c5b8d0799df00684324312181e8d353736","datavalue":{"value":"1209.05071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3557504$5B37C725-BDFA-44FC-8D8C-1130B2056194","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a976ade5b2fcd1915b742e514ee53f356cce213c","datavalue":{"value":"10.1017/S0963548309009663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3557504$FD194F49-3274-43BF-B8AF-BD1B83D3E7B8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a21131a0f408e6a233d7a89a91c68d8d74d5b81","datavalue":{"value":{"entity-type":"item","numeric-id":834612,"id":"Q834612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$97121EBB-F4AD-4F20-8BAA-33656C45FDD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7e2180975cc0441c74630baede04a356d62197c","datavalue":{"value":{"entity-type":"item","numeric-id":290808,"id":"Q290808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$A808E5B3-C7D2-46F5-BC74-099A7B0A42BC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc98aa839a361f8a72b00376d60e99225cffa57","datavalue":{"value":{"entity-type":"item","numeric-id":2703019,"id":"Q2703019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$AFC44D70-F6F3-4F86-8427-1E402EADA7DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"61499de60b4472161f22a83fc07a7ebb72c37d7a","datavalue":{"value":{"time":"+2010-04-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3557504$B184D088-5188-449B-9577-B9324E6162D4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3557504$AE860FD3-6F3D-4CDA-892B-DC284E53FBD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3557504$D3E4E593-D689-4D54-A7FA-98A0B8DC8BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3557504$002E223F-9041-4386-B1D1-3652400EADF4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ebe6451c89211a3b1e50c05f93068c4c78b39d8e","datavalue":{"value":"5700320","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3557504$E24EBF87-3EF1-496B-9E25-86211B433EAD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9675bb37dbeeee484cb314a4abd71e5ae4600c0","datavalue":{"value":"relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3557504$CF37A58E-6664-4102-B7B9-1DCC6D52809F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b8cf60c884317a8de38f6677d430910181dcf50","datavalue":{"value":"proper two coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q3557504$E62901E7-E801-4958-A7DA-9BEE98EAE5F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84f71be9fca46fd3657c068e721360ac552458d2","datavalue":{"value":"monochromatic components","type":"string"},"datatype":"string"},"type":"statement","id":"Q3557504$FAD4C433-70D6-4950-B255-775BDDA3B50B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14968c77d67ef8e029a77937d422ebabbeb27736","datavalue":{"value":"hardness jump","type":"string"},"datatype":"string"},"type":"statement","id":"Q3557504$97CC9FF3-4607-44C2-A308-15EF1790E326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6b3525e6c06e6a6abc0fcd579439e0aa29d595d","datavalue":{"value":"quasilinear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q3557504$BC3AD661-E169-4E7E-816E-399927E6A9CF","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":"Q3557504$CAE23DC3-0FF4-434B-8C44-290341FCD167","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f70f621a5f51517480f229079d940e5c5f1e9a3d","datavalue":{"value":{"entity-type":"item","numeric-id":1850531,"id":"Q1850531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$97CF4FC8-4C9E-4DF8-BB81-9A48AAB5B136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d121cdeb1c638d1e652d84e6b13b6dcfaac9d2b3","datavalue":{"value":{"entity-type":"item","numeric-id":1306426,"id":"Q1306426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$CE73C5EE-6170-4829-B527-1790469F34B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eccf12a6ae2582ef4d7f460d18d2033f9a0e8c8f","datavalue":{"value":{"entity-type":"item","numeric-id":3728016,"id":"Q3728016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$DC8E5900-CB5C-49FB-9691-9C802A0F508E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75be4c9331527d6d2c6ec240d3c34865af1a3458","datavalue":{"value":{"entity-type":"item","numeric-id":885301,"id":"Q885301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$E69BAA24-E1B4-4449-8F34-7D596138B061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9448cd7c9c12beaa07cf7826a7206e0cfc126304","datavalue":{"value":{"entity-type":"item","numeric-id":1316650,"id":"Q1316650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$5F4996D3-25E8-4DED-9AA4-B6F377C48127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b5fa8fb11c78aae21b2eb5b72be3dfa58615b97","datavalue":{"value":{"entity-type":"item","numeric-id":4037693,"id":"Q4037693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$D9B7AEDD-F35D-4FC1-8790-53B881C6B155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb4cd0043520378950644a1497cfc0310df533c0","datavalue":{"value":{"entity-type":"item","numeric-id":1405114,"id":"Q1405114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$886E0FC4-713B-4586-B9BC-37B61620416A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc047fee827268807f48ff95dc135be32e1a536c","datavalue":{"value":{"entity-type":"item","numeric-id":1842168,"id":"Q1842168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$BCAAED9B-D706-488B-B96A-6279B888A1EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2c7865834ab9cd4dbe404352349ae94bf086572","datavalue":{"value":{"entity-type":"item","numeric-id":5441408,"id":"Q5441408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$2062B7B6-DB59-4772-820E-5E989A5AF6C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cacc4cabbabecdcb2babaf46732fee208c4094e","datavalue":{"value":{"entity-type":"item","numeric-id":1400964,"id":"Q1400964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$3B1FB05B-6076-4AE7-83BE-984B47EFC23A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50041fd827b9a880db5475227f379529c471731","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$C04EE646-FE64-4798-B865-0F1B2E2140F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1549e9437c9f5579d91296d6dcdfed15b6805e33","datavalue":{"value":{"entity-type":"item","numeric-id":2709795,"id":"Q2709795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$1631E09A-4755-4A4D-9951-55D5D57368E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e39b7086283a3834e0db09f6b9cef648613cf551","datavalue":{"value":{"entity-type":"item","numeric-id":1323496,"id":"Q1323496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3557504$25B2606F-CA0A-4889-B16E-32510E233FA7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"738ed94cfb04dc70f5fa2525627b739caee5755e","datavalue":{"value":"https://doi.org/10.1017/s0963548309009663","type":"string"},"datatype":"url"},"type":"statement","id":"Q3557504$F9569EA5-6B1F-444E-8B37-0AD39E400D45","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"02097557d3c35901ad9792adeb95e721cdd13b8a","datavalue":{"value":"W2137912301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3557504$EEB08C66-BFF8-4C68-97A4-4CB9291839C5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"622652a448db27db6b94123ac583f818e22bb643","datavalue":{"value":{"entity-type":"item","numeric-id":5449522,"id":"Q5449522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"385de699fc1fca92cc3ee1ca04839a2f7466ce12","datavalue":{"value":{"amount":"+0.99504304","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":"Q3557504$BA403BCD-54D1-4DB1-9E10-CF1F6C56A342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"127f7564f5e4c5466ac1426c45da45c38ee8f849","datavalue":{"value":{"entity-type":"item","numeric-id":6168932,"id":"Q6168932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a396c43a778f2295c5896212b221167f57c3fdf7","datavalue":{"value":{"amount":"+0.87528527","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":"Q3557504$5514A7CB-FCFE-4AE5-806F-BB88A0D83B70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5aeced42f51e19293f37a364dc4ba125d981d94","datavalue":{"value":{"entity-type":"item","numeric-id":4014307,"id":"Q4014307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84dde65691a5745e59f5a9010c7642ee00fa3191","datavalue":{"value":{"amount":"+0.8545512","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":"Q3557504$2419B8C7-9261-483F-BF1E-8FC9593A3724","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92d3ae8f07ab6a6e982904be9d6a6c0c782d1b3c","datavalue":{"value":{"entity-type":"item","numeric-id":3382818,"id":"Q3382818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16391dff8069f80df67cc866c92d86420adcbe8f","datavalue":{"value":{"amount":"+0.8447255","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":"Q3557504$D07BD097-A5EC-49A4-9C1A-285D25238B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bd1f64094b6d224de61ed44a14e43e126ffee5e","datavalue":{"value":{"entity-type":"item","numeric-id":1069951,"id":"Q1069951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d307f82d22ed5c34daa72f94b7b121e10a930639","datavalue":{"value":{"amount":"+0.8442782","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":"Q3557504$EEC0A53A-6B4B-491A-AC09-01423C586BBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eddde88435ea2b4424f5a47b7bd19e467a713033","datavalue":{"value":{"entity-type":"item","numeric-id":2827384,"id":"Q2827384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c371219396fa58edeb535fa020b1d798bb830ecc","datavalue":{"value":{"amount":"+0.84405375","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":"Q3557504$E4B989B0-593C-4B03-96A1-ABF3C4D61B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"009ccf72c3cb9e3c2eb990dee21811188ed3b565","datavalue":{"value":{"entity-type":"item","numeric-id":5963654,"id":"Q5963654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"080d0352f3f4bafb8cbeb76cc1634cb62866b0f9","datavalue":{"value":{"amount":"+0.83948946","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":"Q3557504$81CE3777-52B8-4445-B1F8-ABBE37C71A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88e81a864a5d666a7c91a6389be9d274242f6329","datavalue":{"value":{"entity-type":"item","numeric-id":5002681,"id":"Q5002681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"402e061b4172d08739b638494675e5c7caf41325","datavalue":{"value":{"amount":"+0.8381878","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":"Q3557504$8830031A-7C23-4581-8DBF-3ADB4477E77E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19ca86486705309b4cd62bf7986d549fce4c5d5c","datavalue":{"value":{"entity-type":"item","numeric-id":2931398,"id":"Q2931398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"629f38335f800f320e8fff15ae6c8cfb2509e047","datavalue":{"value":{"amount":"+0.83576995","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":"Q3557504$A0F47D21-F9C2-46C1-BDB0-9811650CC4D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22af9ce8516bf485396eefff569fbeb784812103","datavalue":{"value":{"entity-type":"item","numeric-id":3575151,"id":"Q3575151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"629f38335f800f320e8fff15ae6c8cfb2509e047","datavalue":{"value":{"amount":"+0.83576995","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":"Q3557504$68C7D3CD-B7D2-4A3F-8044-3FD46DF4E374","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3557504","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3557504"}}}}}