Jump to content

Talk:Hedetniemi's conjecture

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia


The image and description for an example of Hedetniemi's Conjecture are misleading.

The description given with the image makes it seem like the tensor product of a 3-cycle and a 5-cycle is the 15-cycle. In fact, their tensor product contains a 15-cycle as a subgraph. In fact, it is impossible for the tensor product of two cycles to be a cycle itself. This is because cycles are 2-regular and the degrees of vertices of tensor products are the products of the degrees of their parent vertices in the factor graphs. This means that C_3 \times C_5 is actually 4-regular and therefore not a cycle. It is still a 3-chromatic graph, but it is not isomorphic to C_15. — Preceding unsigned comment added by 198.37.21.195 (talkcontribs)

You are correct, of course. Fixed. —David Eppstein (talk) 16:04, 21 August 2012 (UTC)[reply]

The original conjecture has now been disproved: https://arxiv.org/abs/1905.02167 "Counterexamples to Hedetniemi's conjecture" and https://www.quantamagazine.org/mathematician-disproves-hedetniemis-graph-theory-conjecture-20190617/ 62.2.246.66 (talk) 08:23, 11 July 2019 (UTC)[reply]

Yes, this article needs to be updated ASAP. — Preceding unsigned comment added by 2a01:e0a:12:f0a0:12b9:b493:c1fa:bf5b (talkcontribs)

Where "needs to be updated as soon as possible" translates to "already was updated over six months ago"? —David Eppstein (talk) 23:38, 21 November 2019 (UTC)[reply]