In Quanta Erica Klarreich recently wrote up Yaroslav Shitov’s new counter example which disproves Stephen Hedetniemi’s 50 year old conjecture, original dissertation, that the number of colors required to color the tensor product of two graphs is the lesser of the numbers used to color the original graphs. These colorings have applications in areas from scheduling to seating plans, and it is clear from Klarreich’s reporting that mathematicians are excited about this result. In fact, Hedetniemi responded very positively when asked by Klarreich about the counter example, saying it “has a certain elegance, simplicity and definitive quality to it.” The counter-example may show Hedetniemi’s conjecture is not true, but Klarreich points out that we do not yet know just how false it is. So, while Shitov has closed one door on this problem, there are still many which are open.
from The Aperiodical https://ift.tt/2RFptPM
Post a Comment