A 53-Year-Old Network Coloring Conjecture Is Disproved

In just three pages, a Russian mathematician has presented a better way to color certain types of networks than many experts thought possible. From a report: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. The tensor product of G and H is a new, larger graph in which each node represents a pair of nodes from the original graphs -- one from G and one from H -- and two nodes in the tensor product are connected if both their corresponding nodes in G and their corresponding nodes in H are connected.Read more of this story at Slashdot.
Click here to read full news..