Mathematician Disproves Hedetniemi’s Graph Theory Conjecture

But now the Russian mathematician Yaroslav Shitov has come up with a simple way to construct such counterexamples: tensor products that require fewer colors than either of their two constituent graphs. Now, if you can color the nodes of the tensor product so that connected nodes are different colors, that will give you a way to form guest lists for different weekends: You can invite the people corresponding to the green nodes on the “green” weekend, the red nodes on the “red” weekend, and so forth, with the assurance that incompatible guests will visit on different weekends. An exponential graph has one node for each possible coloring of G with some fixed number of colors (here, we’re allowing every possible coloring, not just colorings in which connected nodes are different colors).

Source: www.quantamagazine.org