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.
You're reading: Posts Tagged: disproof
Steinberg’s conjecture is false
Conjecture Every planar graph without 4-cycles and 5-cycles is 3-colourable.
Nope!
In a paper just uploaded to the arXiv, Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li and Esteban Salgado show the construction of a graph with no cycles of length 4 or 5 which isn’t 3-colourable: it isn’t possible to assign colours to its vertices so that no pair of adjacent vertices have the same colour, using only three different colours. This is a counterexample to a conjecture of Richard Steinberg from 1976.
The problem was listed in the Open Problem Garden as of “outstanding” importance.
Read the paper: Steinberg’s conjecture is false
via Parcly Taxel on Twitter