Theorists Draw Closer to Perfect Coloring

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.

Perfect graphs are, by definition, colorable with the most limited palette possible. When coloring a graph, every node in a mutually connected cluster, or “clique,” must receive a distinct color, so any graph needs at least as many colors as the number of nodes in its largest clique. In most graphs, you need many more colors than this. But in perfect graphs, you do not. As the French graph theorist Claude Berge defined them in 1961, perfect graphs require a number of colors exactly equal to the size of their largest clique. The “chromatic number” must also equal the “clique number” for every subset of a perfect graph formed by deleting some of its nodes. This perfection rarely arises in the real world, but the property has made perfect graphs much easier to analyze and prove theorems about than their imperfect counterparts.

Yet, after half a century, an obvious question about perfect graphs remains unanswered: How do you actually color them? “Perfect graphs are the graphs that are designed to work well for coloring, so it’s really annoying that we don’t know a good way to color perfect graphs,” said Paul Seymour, a graph theorist also at Princeton. “For a mathematician, a problem like that is a magnet. You want to be able to fix the issue.”

Now, Chudnovsky and collaborators are taking significant steps toward a theorem for coloring all perfect graphs. They have spent the past few years “nibbling off different pieces of the pie,” said Alan Tucker, a mathematician at Stony Brook University, proving coloring theorems for ever-larger subclasses of perfect graphs. This month, in their most general result yet, Chudnovsky, together with Irene Lo,  Frédéric Maffray, Nicolas Trotignon and Kristina Vušković, posted a theorem for coloring all perfect graphs except those containing tricky arrangements of four nodes called “squares.” “It gives confidence that the general case might be solved,” said Gérard Cornuéjols, a mathematician at Carnegie Mellon University.

The hope is that history might repeat itself. Fifteen years ago, researchers raced to prove a theorem establishing the recipe for perfect graphs. After Cornuéjols, Vušković and Michele Conforti proved the theorem for “square-free” perfect graphs in 2001, “the general case came next,” Chudnovsky said.

It was in 2002 that Chudnovsky along with Seymour, then her Ph.D. advisor, and two more collaborators proved the “strong perfect graph theorem” establishing what it takes to be a perfect graph. Their proof, which was published in the Annals of Mathematics in 2006, filled 150 pages. But the strong perfect graph theorem provides a surprisingly simple recipe for perfection: As Berge correctly guessed 54 years ago, a graph is perfect when it does not contain any arrangements of five or more nodes called “odd holes” or “odd antiholes.”

An odd hole is a closed-loop path through part of a graph that passes through an odd number of nodes. (If you drew the graph on paper and cut along this path with scissors, you would cut a hole in the paper.) In an odd antihole, the nodes are connected to all but their nearest neighbors, forming a star-like shape. To see why these oddities render graphs imperfect, consider, for instance, a “five-hole,” which looks like a pentagon: Its clique number is two, since only pairs of consecutive nodes are connected. But try to color the five-hole using only two colors — alternating, for instance, between blue and green — and you soon get into trouble: The fifth node has a blue neighbor on one side and a green neighbor on the other. A third color is needed. (Three-holes, unlike larger odd holes, are allowed to exist in perfect graphs, because their clique number is three.)

Real-world graphs such as conference schedules, the Manhattan subway system or the human neural network typically contain odd holes, making the study of perfect graphs primarily an intellectual exercise. And yet, “the class of perfect graphs allows you to develop sophisticated techniques that you can use in other classes,” said Vušković, a professor at the University of Leeds in the United Kingdom.

Even perfect graphs can be tremendously complex, demanding detailed consideration of each of their umpteen internal structures and seldom submitting to elegant, concise proofs. “The discrete pieces just don’t yield to overall theories,” Tucker said. In their new theorem for coloring all perfect graphs that lack squares (also known as “four-holes”), Chudnovsky, Lo, Maffray, Trotignon and Vušković took a “divide and conquer” approach, essentially breaking the graphs up into parts, coloring the parts, and then gluing them together again.

To color a given graph, their first step is to scour the graph for a structure called a “prism,” which consists of a pair of three-holes connected to each other via three paths.

Next, depending on how the prism attaches to the rest of the graph, the researchers partition the graph into two parts, left and right, with a set of nodes serving as a hinge between them. In general, this hinge might contain a square, but because there are too many possible ways to color hinges with squares, the current proof leaves out these tricky cases.

If either the left or right part contains another prism within it, the researchers must break it up again, and so on until no more prisms remain. (Here, graphs with squares again cause trouble, requiring too many partitions for the coloring procedure to work efficiently.)

Once neither left nor right contain a prism, then they can be colored in. The researchers proved that there is an efficient procedure for coloring both the left part and hinge together and the right part and hinge together. Typically, the two different colorings of the hinge won’t agree; a final step switches the colors of neighboring nodes until they match up.

Now, only cases with squares remain unsolved. Experts disagree about how close the researchers have come to a perfect graph coloring theorem. In Vušković’s opinion, “The square-free case of perfect graphs retains all the structural complexity of the perfect graph. It’s very close to the general case.” Cornuéjols, on the other hand, said, “I think it’s still a big step.”

The five collaborators will meet in Grenoble, France, in December to discuss ways to generalize their proof.

“We did a good step, but there are many steps more to be done,” said Trotignon, a mathematician and computer scientist at École Normale Superieure in Lyon, France. “My feeling now is that this problem will be solved. Before this step of square-free graphs, I would have said no.”

If the researchers succeed in proving a theorem for coloring all perfect graphs, some say it would mark the end of an era. “To me, that’s the last very big open question about them,” Cornuéjols said.

Correction: This article was revised on October 20, 2015, to reflect that the mathematician Claude Berge was from France, not Hungary.

This article was reprinted on Wired.com.