Talk:Hedetniemi's conjecture: Difference between revisions
No edit summary |
No edit summary |
||
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 --> |
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) |
: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) |
Revision as of 08:23, 11 July 2019
Mathematics Unassessed | ||||||||||
|
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)