A 53-Year-Old Network Coloring Conjecture Is Disproved | Mathematics - Quanta Magazine

Photo: Erica Klarreich

Erica Klarreich, writing about mathematics and science summarizes, In just three pages, a Russian mathematician has presented a better way to color certain types of networks than many experts thought possible.

Photo: Olena Shmahalo/Quanta Magazine

A paper posted online last month has disproved a 53-year-old conjecture about the best way to assign colors to the nodes of a network. The paper shows, in a mere three pages, that there are better ways to color certain networks than many mathematicians had supposed possible.

Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, have been a focus of study among mathematicians for nearly 200 years. The goal is to figure out how to color the nodes of some network (or graph, as mathematicians call them) so that no two connected nodes share the same color. Depending on the context, such a coloring can provide an effective way to seat guests at a wedding, schedule factory tasks for different time slots, or even solve a sudoku puzzle.

Graph coloring problems tend to be simple to state, but they are often enormously hard to solve. Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering).

The problem tackled in the new paper seemed, until now, to be no exception to this rule. Unsolved for more than 50 years, it concerns tensor products — graphs made by combining two different graphs (call them G and H) in a specific way...

Over the decades, mathematicians amassed an array of evidence, some of which pointed to the conjecture being true and some to it being false. Mathematicians had different guesses about which possibility would eventually prevail. But everyone seemed to agree, at least, that the problem was a hard one.

“I personally thought the conjecture should be true, because a lot of smart people had looked at it and should have found a counterexample” if one existed, said Anthony Bonato of Ryerson University in Toronto.

Yaroslav Shitov discovered a counterexample to Hedetniemi’s 53-year-old graph theory conjecture.
Photo: Özde Bayer, Max Planck Institute for Mathematics in the Sciences

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. The proof is “elementary, but ingenious,” said Pavol Hell of Simon Fraser University in Burnaby, Canada.
Read more...

Source: Quanta Magazine