{"entities":{"Q1010645":{"pageid":1012493,"ns":120,"title":"Item:Q1010645","lastrevid":57314919,"modified":"2026-03-30T09:38:49Z","type":"item","id":"Q1010645","labels":{"en":{"language":"en","value":"On the quantum chromatic number of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540859"}},"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":"Q1010645$5F42BB4A-559D-4CD2-9EA5-41919547AE28","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"029a0c287eec3b6e2d34f667136a6ec2ee6f25a7","datavalue":{"value":{"text":"On the quantum chromatic number of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010645$19A51D32-A654-4F6E-911E-54E6074D38EC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"099ea6cbbc983c73ef620364caa66928717f13b5","datavalue":{"value":"1182.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010645$19117BEB-9B97-4452-A830-565F7871623E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec54eafd5c64320460e84471f2e246685158025d","datavalue":{"value":{"entity-type":"item","numeric-id":436557,"id":"Q436557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010645$852DAAFA-5A6B-45B9-9EAB-4E253C3EBF88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"59e020aaadd0acbec3b4eaa3c719e595ad3f04ce","datavalue":{"value":{"entity-type":"item","numeric-id":1010644,"id":"Q1010644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010645$E56D4409-FEDE-4894-BBFB-528F7F7C6187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a4efc3823ce8e63228baa4ce6a09f4c0f162ca47","datavalue":{"value":{"entity-type":"item","numeric-id":247315,"id":"Q247315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010645$76E2D039-4318-4350-8F7B-77725333AD5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cbdd3166745b14a9828b7933aca7ae541e4fd11f","datavalue":{"value":{"entity-type":"item","numeric-id":247318,"id":"Q247318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010645$32FE5A94-CFDB-456B-8485-03D2315D46B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6bc2521eae45715fb417b046daabcb23d4401f14","datavalue":{"value":{"entity-type":"item","numeric-id":241258,"id":"Q241258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010645$1DD15BEA-57C1-4BB8-9FD5-4607494BB5B2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010645$B8DB62CC-245F-4EF4-BD11-D4E7FEA8D259","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010645$188743BC-090A-47C7-AAE2-54DAA0A530E7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f095434a6276a534f8f0ed55bd742a60b7e184a6","datavalue":{"value":"https://arxiv.org/abs/quant-ph/0608016","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010645$21E356A4-C74A-4AF3-918F-D97E2580E792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"3fe77c22acba6236a607e21cb578dd4e19a1db72","datavalue":{"value":"https://eudml.org/doc/117191","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010645$BDF2A800-56E0-423B-B892-BA29F7644B8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ad67fb00b67414caee2d629c2468c552a28c6a51","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r81.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010645$7798ABA9-C31E-465F-A5C5-380BB602FCDE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1890b2c99fbda4c2721b1d835ecf6a2deeb25705","datavalue":{"value":"Summary: We investigate the notion of quantum chromatic number of a graph, which is the minimal number of colors necessary in a protocol on which two separated provers can convince a referee that they have a colouring of the graph.   After discussing this notion from first principles, we go on to establish relations with the clique number and orthogonal representations of the graph. We also prove several general facts about this graph parameter and find large separations between the clique number and the quantum chromatic number by looking at random graphs. Finally, we show that there can be no separation between classical and quantum chromatic number if the latter is 2, nor if it is 3 in a restricted quantum model; on the other hand, we exhibit a graph on 18 vertices and 44 edges with chromatic number 5 and quantum chromatic number 14.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010645$81342FE7-74B2-4E7E-95C2-1F8B10B1D4FC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010645$12AE556B-FD2B-4282-B99A-DC0D3911CC34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010645$E539C994-74AA-42F8-A721-C1B7F6713DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010645$95A439F5-3A46-4A65-ACC0-AC35A3279A2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f100e7e9b912dd320a0f918ece3ef4edbbe567fd","datavalue":{"value":"68M12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010645$51A8A852-E09D-4BEA-86F3-49EA50302D8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7af17f227fda8daecc6b4cd26e5d774fa965085f","datavalue":{"value":"81P68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010645$6878E260-3C0E-457C-A5F4-3A938F68DF37","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5cf743b22973d16d5e3a082fcd63ebfd0e577ab","datavalue":{"value":"5540859","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010645$C9CA7B55-8823-4355-B34E-2B2EDE5928E4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe300813e2a0e71de53152e5a95c93633a4f45e5","datavalue":{"value":"quantum chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010645$4D34A79A-9AF8-4F2D-BBBB-03376D7DC3D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010645$4AFF2D9C-E3FC-4091-9F7C-AB24F40016FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2169375ebb26ec0067c3fe2ae2119dcb9b464e","datavalue":{"value":"clique number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010645$580A8132-4BFB-4600-BAE2-A8EFB2F6E0E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71ade1ae350035b973096aa90b5c1b7c94b8fc07","datavalue":{"value":"separated provers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010645$D3AF88A0-4666-470B-8EE7-F55476D270B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010645$EFDA325D-0376-4D90-8C69-57DD0F8B02B1","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":"Q1010645$976D96C2-1CB3-4117-B55B-B3F63E58A6AF","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"abfdfae3b3ecf4f555f77092cb9670576698561d","datavalue":{"value":"bafkreihod4nryie24ifkxjbp7ysvosyw2k2yatqisdwwjwic76pz3q4hwa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010645$31FEE424-FFA9-41A9-A47D-9CE47563CC22","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cc93c4222bf78b931cea3cdc9512f24076327cb","datavalue":{"value":{"entity-type":"item","numeric-id":6173925,"id":"Q6173925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40ade1a8497730a94d348c010e3c9d05ebd26b6d","datavalue":{"value":{"amount":"+0.9422739","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":"Q1010645$F2CCA416-6363-4628-A121-67CC99F1F9B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"464d9ea30726c4557064a74d2d525be6a4e29685","datavalue":{"value":{"entity-type":"item","numeric-id":2326333,"id":"Q2326333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b923dda143303bdf24ad481ae91a3c9d48a1c10","datavalue":{"value":{"amount":"+0.92815727","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":"Q1010645$8A33E26C-5D2F-4788-B15C-2798D6C62EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb07dcdeb79895292a585642b0d325f590a8d84f","datavalue":{"value":{"entity-type":"item","numeric-id":690656,"id":"Q690656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1a2ebe3ec707723be2c5ee8134bf3a2d549690d","datavalue":{"value":{"amount":"+0.91878104","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":"Q1010645$57E02AE5-03E8-4835-859F-F471A1A0D75C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"435abaf21cc0ca3839b90d6588df02d917b5f5bb","datavalue":{"value":{"entity-type":"item","numeric-id":5963425,"id":"Q5963425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0943191fd1b8a1d9eece9cf8cba97bf22fa49f2","datavalue":{"value":{"amount":"+0.91819715","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":"Q1010645$089A3609-08CB-43BB-9BF9-6CBF3F2D3620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6730ece6b6196ad92d5ab82fa8230c6f8f384d3","datavalue":{"value":{"entity-type":"item","numeric-id":1004074,"id":"Q1004074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9903cfc5a2f1bd4fe263b95bdd71a2d869dc76b6","datavalue":{"value":{"amount":"+0.91367793","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":"Q1010645$1817D0E6-1C23-4D46-9B01-22885ED6D796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19eda11abf9b15e3d307fa3acf371819fb6ec145","datavalue":{"value":{"entity-type":"item","numeric-id":5942344,"id":"Q5942344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da98288918cd3ac0ae909f646a9ba477eedf542d","datavalue":{"value":{"amount":"+0.91307634","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":"Q1010645$ED078B33-0735-4FC3-B48F-4A28649112CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c2fa4256ffe682364c435b242b7b83d248bd23b","datavalue":{"value":{"entity-type":"item","numeric-id":2215470,"id":"Q2215470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"663a9d34c4668642e4c272ea76d0256d6fd9e944","datavalue":{"value":{"amount":"+0.9100945","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":"Q1010645$31640E04-E010-452F-8308-C1755A4C6E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d28e813f225bbc5920b60c10b8b60df4c4d44b00","datavalue":{"value":{"entity-type":"item","numeric-id":5257990,"id":"Q5257990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79cdc5a6ccf00dbdd4fe7b34ffb7e11db4758365","datavalue":{"value":{"amount":"+0.90647507","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":"Q1010645$D556853C-6EF9-4598-A874-1955C72F1830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f2d3930fe23f3d5a52a6e6ce5cb717998b55deb","datavalue":{"value":{"entity-type":"item","numeric-id":2716522,"id":"Q2716522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfc66d8e26ec1154ab68d403dd3a597df35d1827","datavalue":{"value":{"amount":"+0.8959839","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":"Q1010645$AC33DE65-80E3-4491-B29F-D21C077D7D2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e57fa8e6c0276c13a73802fdc3b8cf54f3b346d","datavalue":{"value":{"entity-type":"item","numeric-id":4016072,"id":"Q4016072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"101b7fc32cb328420e023ed468bc38251c204619","datavalue":{"value":{"amount":"+0.89497554","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":"Q1010645$B8EF468B-4551-4B30-B247-D5682DFC7005","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1010645","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1010645"}}}}}