Erica Klarreich in Quanta:
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).
More here.