{"entities":{"Q1835680":{"pageid":1846422,"ns":120,"title":"Item:Q1835680","lastrevid":43359289,"modified":"2025-07-25T02:23:19Z","type":"item","id":"Q1835680","labels":{"en":{"language":"en","value":"NP-completeness of a family of graph-colouring problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3794097"}},"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":"Q1835680$564C249A-8EB9-449C-94CE-1E10325EB08F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63be523e4c2401b2b88d873ad0a8662138191753","datavalue":{"value":{"text":"NP-completeness of a family of graph-colouring problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1835680$4C6FDEED-0FF9-4C94-A4F7-9B300C41D831","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"300058bf02b74c29af8d2099c6eaf6a39df24685","datavalue":{"value":"0504.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835680$62946E50-513D-4C7C-B4AB-3ED76EAF19F2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c62ebf6b81a7dc0b00803f76fa35d257aa16b2a3","datavalue":{"value":"10.1016/0166-218X(83)90020-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835680$1F560D90-F3C8-4631-A66A-8ECE640ACE24","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380ba3d7192d4700d42b0d094e27aae962de032","datavalue":{"value":{"entity-type":"item","numeric-id":314432,"id":"Q314432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$6AEED699-45D7-4C31-87FF-F898FD9B8495","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":"Q1835680$91E4A2DD-A135-47E8-9482-3DF5FE8B6AC7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q1835680$E9ECE29D-8F53-471B-9EBC-2FB88CD389A2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835680$39437A38-5E77-412D-890D-DB98C72E9CCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835680$D835A7D5-467C-4BE0-9BF2-7184511E9580","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835680$9FB3D457-55D4-41A2-80EF-8E7257EDAE3B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4d876ba9e90b2dda806058ac32a7e395c26c5b2f","datavalue":{"value":"3794097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835680$90771349-E84C-4FDE-A667-73D7033C34A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2f91296cbef9f0c5c995c1fa0b0e4c0d716c850","datavalue":{"value":"graph colourability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1835680$CFD5058C-F9AD-4963-8964-3A0DE2D836F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1835680$2DA13B2A-FAA2-4B4B-83F5-C1BC64CCF076","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":"Q1835680$C4AD5B5A-5B31-4459-9EB6-7E8859AFDF63","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7979ff647c1295d5fcd90302b401e6e5414a1e96","datavalue":{"value":{"entity-type":"item","numeric-id":1255964,"id":"Q1255964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$F91F4387-06F3-40EC-9BEB-2506EF33D184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"519c04edb24aef1ce88b720e46082a964b292326","datavalue":{"value":{"entity-type":"item","numeric-id":3281090,"id":"Q3281090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$2E406125-6FF6-453E-9835-3A2C678F587A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc4f0630ec86e5a0d3e96a9ce7ec4c2915d07620","datavalue":{"value":{"entity-type":"item","numeric-id":4083458,"id":"Q4083458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$D1B00D10-BB5C-44FB-B1C2-8F35D8531F81","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":"Q1835680$673CE6DF-5BD5-4A4F-805F-1D4C31347320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$6DEC8AD5-E807-49FB-8DF3-B961759DD202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82bd142382c48198bd3d062596f9da54dc955038","datavalue":{"value":{"entity-type":"item","numeric-id":1230631,"id":"Q1230631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$068A392E-F574-4585-9278-18DDE2DC393E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e4db718337c47f930eac480f7f0beee5c7871d7","datavalue":{"value":{"entity-type":"item","numeric-id":5554997,"id":"Q5554997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$A0DE3B7B-4C16-4189-999E-08A1E2B8AA14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a19db9ac81b41bda4141d0a8537b5930e583d51","datavalue":{"value":{"entity-type":"item","numeric-id":4405185,"id":"Q4405185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$ACC4ED45-A978-418B-BC76-EB4AF430064D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c428f1852e95384416608cd782a84ad75e86d42b","datavalue":{"value":{"entity-type":"item","numeric-id":755592,"id":"Q755592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$EF8022D8-1AE1-403B-87D6-5AA1DC0D8774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9481402bdcb1768d6c5f1db5712458103c05e5c","datavalue":{"value":{"entity-type":"item","numeric-id":2556423,"id":"Q2556423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$F419DBDA-0CAC-4ADD-8BC1-77A5D4B562AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bd1435c3b8019d52e6a1caffa9d9c76a380c1d","datavalue":{"value":{"entity-type":"item","numeric-id":1212006,"id":"Q1212006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835680$AEB1F9FA-95F9-47C4-9E1A-251B002762BE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1835680","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1835680"}}}}}