{"entities":{"Q2151188":{"pageid":2161931,"ns":120,"title":"Item:Q2151188","lastrevid":54354392,"modified":"2026-01-26T16:48:35Z","type":"item","id":"Q2151188","labels":{"en":{"language":"en","value":"The chromatic number of the product of 14-chromatic graphs can be 13"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7551318"}},"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":"Q2151188$7769D72F-61C0-4BF0-B68F-7678B601C9B4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e1b7181e01e6e059075f0744516e12ba6b288775","datavalue":{"value":{"text":"The chromatic number of the product of 14-chromatic graphs can be 13","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2151188$ED01F35A-0462-4845-8B84-7DE70CD701D3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1363ae1d9d703f7fb2acd3ca733e972bbcaf0fee","datavalue":{"value":{"entity-type":"item","numeric-id":178714,"id":"Q178714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$6B1259C7-1929-4CB0-8892-B4C46CD3CC6B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$B96F6A06-9EFA-4C21-97CD-2159E987272D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"faa08a6e70c7dd841bb2fd29d4bbc1d6e2960f95","datavalue":{"value":{"time":"+2022-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2151188$6395E295-93F9-4EE3-B17F-59D5E9B27825","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"413e0b9d25b9e16483d7adb2af7059f2ef23d736","datavalue":{"value":"In this paper, the author refutes Hedetniemi's conjecture for even small chromatic numbers. He called a graph \\(K\\) multiplicative if it satisfies the following property: If \\(G\\times H\\) admits a homomorphism (i.e., an edge-preserving map) to \\(K\\), then \\(G\\) or \\(H\\) admits a homomorphism to \\(K\\) (the product is the categorical product). Hedetniemi's conjecture is the statement that the complete graph \\(K_n\\) is multiplicative for every \\(n\\). The main result of this paper is the following: For \\(n\\geq 13\\), \\(K_n\\) is not multiplicative, i.e., there exist graphs with chromatic number larger than \\(n\\) whose product has chromatic number \\(n\\). The construction is an adaptation of the construction of counterexamples to Hedetniemi's conjecture devised by \\textit{Y. Shitov} [Ann. Math. (2) 190, No. 2, 663--667 (2019; Zbl 1451.05087)], and adapted by \\textit{X. Zhu} [J. Comb. Theory, Ser. B 146, 141--150 (2021; Zbl 1457.05095)] to graphs with relatively small chromatic numbers. The new tools introduced here are graphs with minimal colorings that are ``wide'' in the sense of \\textit{G. Simonyi} and \\textit{G. Tardos} [Combinatorica 26, No. 5, 587--626 (2006; Zbl 1121.05050)], and generalised Mycielskians to settle the case \\(n= 13\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2151188$7C5D193D-A2F9-4C89-8EB1-245806BA9F22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151188$2E9D4549-5858-44C3-A75D-03C6659D4168","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e2c5a192d2f6b94df2ec5bb7d03355efe859836","datavalue":{"value":"7551318","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151188$CD001A8E-C5AB-4DBC-8E43-C0D37386191E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2151188$12523CF2-9027-41BA-BA7A-EFDC19DF089E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ecdbe082d1eeff1e1b20a5ed94da2b6838664b9","datavalue":{"value":"graphs with minimal colourings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2151188$574195CC-BE2F-495A-BB2F-FE2E6C806B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5c65c63441f9e6828a1d29074b9a17cd9b8e459","datavalue":{"value":"generalised Mycielskians","type":"string"},"datatype":"string"},"type":"statement","id":"Q2151188$B8F27378-EDF3-4D52-86FD-617D299F9305","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$ADB416A9-39BC-4108-B2B6-50C58357B726","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":"Q2151188$A7EC09DE-DBEB-4F8B-80C4-3F0538F12AF7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"10eda204b3e7259218fb221c50d9de6e9a8f1960","datavalue":{"value":"https://doi.org/10.1007/s00493-021-4781-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q2151188$F9AD9609-DB11-4221-9300-8451F5735894","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99827cec6c053fa49e763db723d7589ce9739962","datavalue":{"value":"W4221033132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151188$BBCF99B9-BDB4-4D58-8EC6-526A32F50F4E","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":"Q2151188$31B0A0B7-533F-4AC0-A20B-FAFF59F45257","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":"Q2151188$FD2061A9-7A97-42D3-99F8-EBB2472A54C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e60738baba345d0233fd73b9523456280ab40d43","datavalue":{"value":{"entity-type":"item","numeric-id":4736765,"id":"Q4736765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$3CA40442-E3A3-42A2-9EA8-C66D296A6BFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c851f18062257490df5b64d4306a128287463c79","datavalue":{"value":{"entity-type":"item","numeric-id":4352272,"id":"Q4352272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$17D0271E-9F4D-4782-8B20-EC5D364E52B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4279bba66ea306b66cd2be18fa8491eb99df393","datavalue":{"value":{"entity-type":"item","numeric-id":1043947,"id":"Q1043947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$C4726618-A128-4ABF-B098-F410CDB2686B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fed138e639465ff110a81d0133db4a6eeca574c","datavalue":{"value":{"entity-type":"item","numeric-id":2221935,"id":"Q2221935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$89EA425E-24EE-4FB6-8763-0C5A44099868","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":"Q2151188$522CD9E1-97D6-468A-BBA8-B95AFA707CCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89e689e6859890bb168fff9696457c05f3c55367","datavalue":{"value":{"entity-type":"item","numeric-id":2274002,"id":"Q2274002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$F55BAC2F-E964-4B15-899B-5318573B4869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efa487b0e966ba4f9bf94b658fa64576034b6ea3","datavalue":{"value":{"entity-type":"item","numeric-id":879165,"id":"Q879165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$62032AC9-60FD-423E-BE1E-7885A8657980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddba55a4cb75b7398b0a533e0f9c3dd429229bcc","datavalue":{"value":{"entity-type":"item","numeric-id":2278108,"id":"Q2278108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$FB0E9432-E0A2-452A-AC4E-B4BBCA1C347D","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":"Q2151188$28DE77D8-CFEE-4D27-A124-FEFCC38C1211","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ba17796fed6d0ab647b7f2f1e6614bad817aab0","datavalue":{"value":{"entity-type":"item","numeric-id":782938,"id":"Q782938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$572DB027-CAC3-4630-9532-BA5BA5B0C5CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fd896c7b7423ece4570e0b96f81d34308584ad7","datavalue":{"value":{"entity-type":"item","numeric-id":2221923,"id":"Q2221923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2151188$F733AD30-5346-45F7-89F9-65DCDF307002","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec6293500385c0729b6389a7d32ae42a81af1ab7","datavalue":{"value":"10.1007/S00493-021-4781-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2151188$0BE5D1BA-ECFB-4BE6-975F-C8671A07FCDC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1d770e67e276848ba06479b7801c1eb8eb55b1e","datavalue":{"value":{"entity-type":"item","numeric-id":2274002,"id":"Q2274002"},"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":"Q2151188$311231F7-CA08-447E-86E0-E645313B088A","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":"a94550b4a0b594c4725bf4170f607163def0b7eb","datavalue":{"value":{"amount":"+0.8695400357246399","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":"Q2151188$DB5E683A-BF72-4BA9-8E95-D3965BE1A495","rank":"normal"},{"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":"7c05d3e5784dd9a8551a999e77d4c8fbc31b78fa","datavalue":{"value":{"amount":"+0.858139157295227","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":"Q2151188$68E0EBE9-837E-4FDF-B089-AFE72CD3805D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d38820d0de01069a1e2bc8c658cfdd17429a4517","datavalue":{"value":{"entity-type":"item","numeric-id":1387740,"id":"Q1387740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83c28ef1f3ee4c7ea455f4a99ef8ed8b49ac17e5","datavalue":{"value":{"amount":"+0.8464378118515015","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":"Q2151188$806EE990-E021-4D96-970B-19BCFD64FD5F","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":"83c28ef1f3ee4c7ea455f4a99ef8ed8b49ac17e5","datavalue":{"value":{"amount":"+0.8464378118515015","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":"Q2151188$21A9EF9F-8001-4B67-B178-29EEEDD62D0F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2151188","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2151188"}}}}}