 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
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 (talk • contribs)
- You are correct, of course. Fixed. —David Eppstein (talk) 16:04, 21 August 2012 (UTC)
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)
Yes, this article needs to be updated ASAP. — Preceding unsigned comment added by 2a01:e0a:12:f0a0:12b9:b493:c1fa:bf5b (talk • contribs)
- 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)