A theorem for coloring a large class of “perfect” mathematical networks could ease the way for a long-sought general coloring proof

Natalie Wolchover in Quanta:

Four years ago, the mathematician Maria Chudnovsky faced an all-too-common predicament: how to seat 120 wedding guests, some of whom did not get along, at a dozen or so conflict-free tables. Luckily, the problem fell squarely in her realm of expertise. She conceived of the guests as nodes in a network, with links between incompatible nodes. Her task was to color in the nodes using a spectrum of colors representing the different tables. As long as connected nodes never had the same color, there would be no drama at the reception.

As a master of this pursuit, known as “graph coloring,” Chudnovsky did the whole thing in her head and finished the seating chart in no time. “My husband was very impressed,” she said.

Networks of related objects, be they nodes or wedding guests, are known to mathematicians as “graphs,” and graph coloring is the much-studied act of partitioning these objects into conflict-free sets. Most graphs, with their tangle of interconnections, are impossible to color with a limited palette. The larger they are, the more colors you need. Moving from node to node, alternating between colors, you inevitably get into traffic jams that force you to pull new hues out of the box. Likewise, in the real world, seating charts, meeting schedules and delivery routes can seldom be made optimal. But since the 1960s, mathematicians have escaped these coloring frustrations by working with so-called perfect graphs, which “behave very nicely with respect to coloring,” said Chudnovsky, a 38-year-old math professor at Princeton University.

More here.