Tinged with Significance: To Color the Perfect Graph

April 3, 2009

How many colors color a "perfect" graph so that connected dots are always different colors?

"Unfortunately, the graph-coloring problem is nearly impossible to answer in full generality," Julie Rehmeyer wrote in Science News. "But after decades of effort, a team of mathematicians has managed to characterize one major class of graphs for which they can solve the problem: the graphs that are 'perfect.'"

Suppose a group of nodes exists in which every node is connected to every other node, Rehmeyer noted. Every node in that group will need to be a different color. This means that a graph will need at least as many colors as there are members in the largest such interconnected group, and sometimes more. If this number of colors (called the clique number) is enough, the graph is called perfect.

Determining which graphs are perfect, however, is no simple matter. In 1960, Claude Berge conjectured that a graph with two particular characteristics is perfect. But he couldn't prove his conjecture.

The answer finally came in 2006, when Paul Seymour of Princeton University, Robin Thomas of the Georgia Institute of Technology, Neil Robertson of Ohio State University, and Maria Chudnovsky of Columbia University published a proof. Chudnovsky presented the work at the Joint Mathematics Meetings in Washington, D.C., in January.

"It's a brilliant proof," said Gerard Cornuejols of Carnegie Mellon University and Universite d'Aix-Marseille. He had provided some of the ideas that the successful team used to crack the conjecture. To encourage work on the problem, Cornuejols had also offered $5,000 of his own money for a proof, which the team subsequently collected.

More kinds of graphs, however, remain to be colored; and mathematicians continue to look for algorithms to efficiently detect perfect graphs and for methods to find the minimal coloring the Berge's "strong perfect graph theorem" has shown must exist.

Source: Science News, March 6, 2009.