{"entities":{"Q1387740":{"pageid":1398480,"ns":120,"title":"Item:Q1387740","lastrevid":68599209,"modified":"2026-04-13T00:50:04Z","type":"item","id":"Q1387740","labels":{"en":{"language":"en","value":"A survey on Hedetniemi's conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1160425"}},"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":"Q1387740$81BB9A3D-878D-4785-B804-9526BCD644C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"26e0792fbc3e6f9a41d3cfabe8f196568b4ab343","datavalue":{"value":{"text":"A survey on Hedetniemi's conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1387740$16650B52-DFEF-48C8-8BA2-CDF854CD50D6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"815e0a7a12c9850983f92499eed094fa25185e24","datavalue":{"value":"0906.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1387740$87A8781F-5A11-4FEF-90B1-806A035FE7D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6b19b09c7519f38384d021f845694abb1cfab04","datavalue":{"value":{"entity-type":"item","numeric-id":168189,"id":"Q168189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1387740$10BCAC29-6E0D-4B07-930E-E8F2312785D2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fc770cd89d4fae0e8d7b267c7a43d9a33ef28782","datavalue":{"value":{"entity-type":"item","numeric-id":168175,"id":"Q168175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1387740$A3A70CF9-B877-4915-9C81-E366F2158865","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"434673b5be884fc3474ad3e71a8cb592da1960eb","datavalue":{"value":{"time":"+1999-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1387740$EFCE1230-4829-45E4-90C2-804A8A84C48E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ddad68e66b4dbb9bd59335c0b134571a8f2fedc","datavalue":{"value":"The product \\(G\\times H\\) of the graphs \\(G\\) and \\(H\\) has vertex set  \\[ V(G\\times H)= \\{(g, h)\\mid g\\in V(G)\\text{ and }h\\in V(H)\\} \\]  and edge set  \\[ E(G\\times H)= \\{(g, h)(g', h')\\mid gg'\\in E(G)\\text{ and }hh'\\in E(H)\\}. \\]  It is easily seen that \\(\\chi(G\\times H)\\leq \\min\\{\\chi(G), \\chi(H)\\}\\); \\textit{Hedetniemi} [University of Michigan Technical Report 03105-44-T (1966)] conjectured that equality holds for all finite simple graphs \\(G\\) and \\(H\\). An equivalent formulation is given by \\(C(n)\\): If graphs \\(G\\) and \\(H\\) are not \\(n\\)-colorable then the product \\(G\\times H\\) is not \\(n\\)-colorable. Hedetniemi [ibid.] proved \\(C(2)\\). \\textit{M. El-Zahar} and \\textit{N. W. Sauer} [Combinatorica 5, 121-126 (1985; Zbl 0575.05028)] gave a complicated proof of \\(C(3)\\); the conjecture is open for \\(n\\geq 4\\). The author gives a somewhat simplified version of their proof and then discusses results and problems related to the conjecture.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1387740$75D975C2-343A-47C6-AE11-2F4E2D8BEF2D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1387740$53DC90F6-DEA1-4616-88E9-89CE0C1C3324","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"161f0770f9ba3a909094efd339cf2fc3d0549dfd","datavalue":{"value":"1160425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1387740$0A27A040-0105-46C8-B444-311BD5D75A0A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"600bbb06e97e6606c9effff6f2c763b132036bec","datavalue":{"value":"Hedetniemi's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1387740$CCD647C6-B38E-4B73-81D5-5DFEA6DF51F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1abf3da2f34e75cf538253fb340bad1e1a06bed4","datavalue":{"value":"\\(n\\)-colorable","type":"string"},"datatype":"string"},"type":"statement","id":"Q1387740$720AA0B5-CAA1-4FCC-BB00-5229E45AF187","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4160ba73cc613e2769e008ae8a9ce69c96d8603f","datavalue":{"value":{"entity-type":"item","numeric-id":207053,"id":"Q207053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1387740$D3B27E56-8E4C-4480-80FF-F08A71687A94","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":"Q1387740$B4D13D57-C329-4702-99D8-47AB3615F8E8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f5e799f8858b96366c95e5630a849bd53e022a9c","datavalue":{"value":"https://doi.org/10.11650/twjm/1500406890","type":"string"},"datatype":"url"},"type":"statement","id":"Q1387740$F1411FCC-5887-4D76-8093-E71A7EA83657","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"236189854a3f7e5e353ec6966e923fbef4fb062d","datavalue":{"value":"W1483461381","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1387740$5F1A99E6-BFD5-4F44-9659-FB6D72C83214","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"17a4d6e94c9daa0cce367165cda307127149affe","datavalue":{"value":"Q123154756","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1387740$AEFD32BA-838D-4F76-A448-EA7412561E46","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe687fea6c132f29cfabdc8c7d55ab269fb95b5c","datavalue":{"value":"10.11650/TWJM/1500406890","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1387740$AF6E63D3-A03C-4308-B4BB-7B287D6FAEAC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9434dc4fa1878e7ed967f3c54e0c3305049504e0","datavalue":{"value":{"entity-type":"item","numeric-id":3815317,"id":"Q3815317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ce48b3478448f6fef574887b82dad1b853c6cdc","datavalue":{"value":{"amount":"+0.9346582889556884","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":"Q1387740$4F801FB4-5B57-45E5-ADC8-7A38927456DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af6cd1c7b8f9d4a8b03190e2dbc39a9889288de6","datavalue":{"value":{"entity-type":"item","numeric-id":5931456,"id":"Q5931456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c7bbbe395115b1e98f72dec5e860859e434323d","datavalue":{"value":{"amount":"+0.9182762503623962","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":"Q1387740$43C6234A-AF7C-497E-B5D4-CEB9B42864CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6313fa1c337f65599a6f8b65e2a9b5e6f6bf8db","datavalue":{"value":{"entity-type":"item","numeric-id":4225439,"id":"Q4225439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da1fc5e5cc70ba9057e1110e705bb1029bd4d618","datavalue":{"value":{"amount":"+0.8888508677482605","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":"Q1387740$2B354AE8-7FE3-4915-95D6-FC847BFD97CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eea24b808e7118d8f0a00f533dad3e74cacdc675","datavalue":{"value":{"entity-type":"item","numeric-id":4020700,"id":"Q4020700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65d56b79804a0d49465965a1ff924660ebfe5118","datavalue":{"value":{"amount":"+0.8828715682029724","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":"Q1387740$C4020CBF-F698-4C33-AC72-290DE74E7B18","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A survey on Hedetniemi's conjecture","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_survey_on_Hedetniemi%27s_conjecture"}}}}}