Talk:Hedetniemi's conjecture: Difference between revisions

Content deleted Content added

Inline

Revision as of 08:23, 11 July 2019

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's priority scale.

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)[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]

@@ Line 7: / Line 7: @@
 It is still a 3-chromatic graph, but it is not isomorphic to C_15. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:198.37.21.195|198.37.21.195]] ([[User talk:198.37.21.195|talk]] • [[Special:Contributions/198.37.21.195|contribs]]) </span></small><!-- Template:Unsigned -->
 :You are correct, of course. Fixed. —[[User:David Eppstein|David Eppstein]] ([[User talk: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/ [[Special:Contributions/62.2.246.66|62.2.246.66]] ([[User talk:62.2.246.66|talk]]) 08:23, 11 July 2019 (UTC)