{"entities":{"Q2274002":{"pageid":2284745,"ns":120,"title":"Item:Q2274002","lastrevid":57824712,"modified":"2026-04-02T16:50:50Z","type":"item","id":"Q2274002","labels":{"en":{"language":"en","value":"Counterexamples to Hedetniemi's conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7107185"}},"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":"Q2274002$D338F18E-63F4-4404-B16F-442C1F3128C8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4b564103acab0eb39c37875cd55d345ac4b760c8","datavalue":{"value":{"text":"Counterexamples to Hedetniemi's conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2274002$81F9CA99-37B5-44D3-B335-E1FF0A0B69F9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dd610a94e58bec50b4358fd0d8401c255dc1377d","datavalue":{"value":"1451.05087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2274002$CC4348DA-D614-48C4-B742-F31D66AACC1F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"553c7ad508f4615999d4ef926cfdf75d436f510c","datavalue":{"value":{"entity-type":"item","numeric-id":175062,"id":"Q175062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$C30256C7-C821-4C0D-B82B-C50EA3BAECB1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"47982c139c41a713484decefc5a5dde8b3533371","datavalue":{"value":{"time":"+2019-09-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2274002$EC903837-3B38-4A51-9089-94C04752DB09","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a84b75e199876b8d4e273ef1173528c2a06ac696","datavalue":{"value":"https://arxiv.org/abs/1905.02167","type":"string"},"datatype":"url"},"type":"statement","id":"Q2274002$58DE4FBD-CB76-423C-9A35-D51D3B3294BF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a6b366d1fe18eb6d5d3723f1f0377def933524e5","datavalue":{"value":"The chromatic number \\(\\chi(G)\\) of a graph \\(G\\) is the least number of colours required to colour the vertices of \\(G\\) such that adjacent vertices receive different colours. The tensor product of finite simple graphs \\(G\\) and \\(H\\), denoted by \\(G \\times H\\), is the graph with vertex set \\(V(G)\\times V(H)\\) such that \\((u,v)\\) and \\((x,y)\\) are adjacent if and only if \\(u\\) and \\(x\\) are adjacent in \\(G\\) and \\(v\\) and \\(y\\) are adjacent in \\(H\\). It is easy to see that \\(\\chi(G \\times H) \\leq \\min\\{\\chi(G), \\chi(H)\\}\\). \\textit{S. T. Hedetniemi} [Homomorphisms of graphs and automata. Techn. Rep. 0310544-T, Ann Arbor, MI: University of Michigan (1966)] conjectured that equality holds for all \\(G\\) and \\(H\\). This important conjecture has attracted much attention in more than five decades, and it has been confirmed in many special cases. In this paper, the author disproves this conjecture by showing the existence of infinitely many counterexamples.   The strong product \\(G \\boxtimes H\\) is the graph with vertex set \\(V(G)\\times V(H)\\) such that \\((u,v)\\) and \\((x,y)\\) are adjacent if and only if one of the following holds: \\(u=x\\) and \\(v\\) and \\(y\\) are adjacent in \\(H\\); \\(v=y\\) and \\(u\\) and \\(x\\) are adjacent in \\(G\\); \\(u\\) and \\(x\\) are adjacent in \\(G\\) and \\(v\\) and \\(y\\) are adjacent in \\(H\\). Given a finite graph \\(\\Gamma\\) (possibly with loops) and a positive integer \\(c\\), the exponential graph \\(\\mathcal E_{c}(\\Gamma)\\) is the graph with all mappings \\(V(\\Gamma) \\rightarrow \\{1, 2, \\ldots, c\\}\\) as vertices such that two distinct mappings \\(\\phi\\), \\(\\psi\\) are adjacent if and only if the condition \\(\\phi(u) \\neq \\psi(v)\\) holds whenever there is an edge of \\(\\Gamma\\) between \\(u\\) and \\(v\\). The author proved that, for \\(c = \\lceil 3.1q \\rceil\\) with \\(q\\) a sufficiently large integer, and for any graph \\(G\\) with girth at least \\(6\\) and fractional chromatic number strictly greater than \\(3.1\\) (the existence of \\(G\\) is guaranteed by a classic result of \\textit{P. Erd\u0151s} [Can. J. Math. 11, 34--38 (1959; Zbl 0084.39602)]), the graph \\((G \\boxtimes K_{q}) \\times\\mathcal E_{c}(G \\boxtimes K_{q})\\) is a counterexample to Hedetniemi's conjecture, where \\(K_{q}\\) is the complete graph of order \\(q\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2274002$C26B1CE8-C6FC-48FF-B23E-D19A8C280B4E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7158b5944987d3c0b8ee46fd0153ef79727facc8","datavalue":{"value":{"entity-type":"item","numeric-id":201997,"id":"Q201997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$29FF18CA-B593-4A4C-9C85-BD26BF0E0731","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2274002$9CA75902-1DE4-4FCF-95FC-0FD1E850CFDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2274002$31679B19-7653-43A9-9B0E-DAFB9325024C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"721dea3c6631d2eb0307d8071c7508a2db676c17","datavalue":{"value":"7107185","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2274002$0661B276-45B6-4D53-9471-772B7D3135DA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2274002$FDAA8230-C3CA-449F-8F1F-6CD823DDBC24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09085508750880ac95f1a6c3c9ee02f8123fbe7d","datavalue":{"value":"tensor product of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2274002$A280E151-CE88-43BE-9525-7F994C3E8AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"600bbb06e97e6606c9effff6f2c763b132036bec","datavalue":{"value":"Hedetniemi's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2274002$CEEBE1EF-858A-47E3-97F2-1DBD7C81111E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a1ce4cc1f9802bb4527b2cffc5f7f2e320dc4eb2","datavalue":{"value":"Q122932603","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2274002$10CA99BC-97D0-481C-A5C5-31ED6B7BE73B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c848be20a9df9788b716f450ec8f21487ece7c32","datavalue":{"value":{"entity-type":"item","numeric-id":1668077,"id":"Q1668077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$F04CD696-0D5D-4186-BDD7-D125B80B4E4C","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":"Q2274002$BF69194E-BF8E-4142-844D-9B7DACC95F8C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8823edbd92aaaacad4d4939bdc13d1dc9111ab78","datavalue":{"value":"W2969838569","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2274002$0716164B-B502-4A10-8B0D-CBF7745240B0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a77aede59be4b803b6ac3243e7cd043adf51082d","datavalue":{"value":{"entity-type":"item","numeric-id":4100121,"id":"Q4100121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$9FC0563B-12F1-40DA-A93C-3A132D8B9090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99b23c5616fca5ce7e6cc41d1a4fedcfd3c84f11","datavalue":{"value":{"entity-type":"item","numeric-id":3815317,"id":"Q3815317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$05E33604-B2DD-42F4-9DA5-CD70B82A9507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c36a5b400cc220f1343819efbe053be19779966c","datavalue":{"value":{"entity-type":"item","numeric-id":1063620,"id":"Q1063620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$C3012417-065F-4031-A8AC-3AA83D06DDDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$18BADCD4-C0AB-4D47-9DEC-A5D6004E0081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5028065ceb61d7fbbcc8d74c873e6a965e0cc43f","datavalue":{"value":{"entity-type":"item","numeric-id":1110530,"id":"Q1110530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$D4AB01B8-A910-4B74-868E-C61294328D9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1dbed3e5b77f3a7b7845cc8866e59497307ae09","datavalue":{"value":{"entity-type":"item","numeric-id":530765,"id":"Q530765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$EC86AB6E-B9CD-4243-8FFB-629C55590249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b719e6a72b012e14fbf6f64ccfc44a51e5485f46","datavalue":{"value":{"entity-type":"item","numeric-id":1063621,"id":"Q1063621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$22B70B38-4E9E-4F60-BB45-64274C974AA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee7e39a9b0f8ed4bb35a869ed8b616b6bbde5d0d","datavalue":{"value":{"entity-type":"item","numeric-id":1923489,"id":"Q1923489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$F3F56F6D-5EF9-4EC3-9E80-0B16E0647E63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54ca7e5ae6667e96acfd619e4c06fe19f1e03475","datavalue":{"value":{"entity-type":"item","numeric-id":1158161,"id":"Q1158161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$C34F58D4-9F8E-4492-B676-86EE938F9FF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8798eca6d8e7b3ad2d2774cc9db76087056c7","datavalue":{"value":{"entity-type":"item","numeric-id":5931456,"id":"Q5931456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$496A0D2B-0165-47EF-8F31-029936A1BC9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"037ac89164440ab2024e2f294e450bb15082e61d","datavalue":{"value":{"entity-type":"item","numeric-id":2573651,"id":"Q2573651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$7818A607-6C08-4C7B-A1ED-A38D77793F1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac006511e7c75b6654835b044b47d3834f10dd2b","datavalue":{"value":{"entity-type":"item","numeric-id":509108,"id":"Q509108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$D9C5861C-7F70-4204-9E19-72EB0613AB6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c93292ef7a90016ce9aca863e2b3d13dc6ec482c","datavalue":{"value":{"entity-type":"item","numeric-id":2509308,"id":"Q2509308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$3470C58D-6DB4-4AC9-A658-9D07B64320C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccbb2b9035e545c37b778a0955a9777fcf8a5fd1","datavalue":{"value":{"entity-type":"item","numeric-id":798680,"id":"Q798680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$EF87508A-35ED-4ED4-AF0E-BA0AB9C11511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26d0bb924778b6fbfb16269ddf2962ef350b35ab","datavalue":{"value":{"entity-type":"item","numeric-id":2338641,"id":"Q2338641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$08A0D300-4613-45B2-9D27-D08DF07B9EAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb95167040e5dd81ffce219710d36ad0cf036502","datavalue":{"value":{"entity-type":"item","numeric-id":1387740,"id":"Q1387740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$747A53CB-5F18-485B-BC48-1FB72D6A862A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b7f65c77fff55cb011dc2041417cd0741085391","datavalue":{"value":{"entity-type":"item","numeric-id":648973,"id":"Q648973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2274002$1CF8AA09-5519-4859-8FAF-998176F12930","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"07da64449b76a240f39a02b6982da2a27110630a","datavalue":{"value":"10.4007/ANNALS.2019.190.2.6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2274002$49B13B5E-DA7A-4FDD-B62D-CB756A72BECF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5616c15465d44bc664f0fc1d40c0bd64ad96ee9c","datavalue":{"value":{"entity-type":"item","numeric-id":2084794,"id":"Q2084794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebc5fa9fcf8c451a3fc16f0a28b1f38f25eb4311","datavalue":{"value":{"amount":"+0.914573073387146","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":"Q2274002$283606A4-78C8-4CB7-BC2B-81E88550AE6A","rank":"normal"},{"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":"ae84dd2d0b669ab219ba9a4476dc436eb90eb147","datavalue":{"value":{"amount":"+0.9130783081054688","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":"Q2274002$E0B80D2E-F309-4B19-BDE0-C367E66BB75C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38456ed64ea20376cc40303ec846c27f88a73caa","datavalue":{"value":{"entity-type":"item","numeric-id":2221923,"id":"Q2221923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d69715f5909d97a31e9252d4efa1144624634b81","datavalue":{"value":{"amount":"+0.9087221026420592","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":"Q2274002$F5E3ECCF-59C9-45D6-B6C4-2847DC015FAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fe94ef9b1d0079b7e350a9eb23b2aa38e346341","datavalue":{"value":{"entity-type":"item","numeric-id":2151188,"id":"Q2151188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41e000366e154e3a2c271f3a453552317ba88744","datavalue":{"value":{"amount":"+0.8720574975013733","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":"Q2274002$6DA4BA34-8B2B-4CF8-817F-6349FC94D1D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e6dea657295900cf70b3fcfc7fa279bb35dde0c","datavalue":{"value":{"entity-type":"item","numeric-id":2221935,"id":"Q2221935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6eeb30bdd39ecfd606b9a02b04c9fd9ea40efe27","datavalue":{"value":{"amount":"+0.8701051473617554","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":"Q2274002$BF1C98C9-1A07-4A1D-ABC8-C93CB691366A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2274002","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2274002"}}}}}