Read articles, including Science News stories written for ages 9-14, on the SNK website.
• Contents
• Better chow yields more milk: A more nutritious form of corn for dairy cows boosts farm profits, teen investigator finds
• Fuzzy future: Kids may suffer impaired vision from spending too little time outdoors, studies suggest
• Building with moon rocks: Working on the moon with lunar soil and grit could prove easier, more efficient and less costly than using earthly materials
The four color problem gets a sharp new hue
Mathematicians find new answers to the still puzzling theorem that four colors suffice to color any map.
A+ A- Text Size

In 1852, botanist Francis Guthrie noticed something peculiar as he was coloring a map of counties in England. Despite the counties’ meandering shapes and varied configurations, four colors were all he needed to shade the map so that any two bordering counties were different colors. Perhaps, he speculated, four colors were enough for any map.

Little did Guthrie know the load of trouble he unleashed with his innocent conjecture. It took mathematicians nearly a century and a quarter to prove him right, and even that wasn’t enough to close the Pandora’s box Guthrie had opened. Mathematicians pulled out their markers and tried to color everything in sight.

The particular things mathematicians wanted to color were graphs: dots connected by lines Such graphs can be used to describe everything from friendships to the Internet to gene interactions. They can even describe maps, if the countries correspond to dots and bordering countries are connected by lines. Graphs from maps have the special property that the lines will never cross, though other graphs can form hairballs as nasty as you please. How many colors, mathematicians wondered, would it take to color any graph so that connected dots are always different colors?

That question turns out to be surprisingly important, and not just to a few marker-crazed mathematicians. Cell phone companies, for example, need to assign separate channels to any two transmitters whose ranges overlap in order to avoid interference. Naturally, they’d like to use the smallest number of channels for the job. Turn the transmitters into dots (called nodes), connect the nodes with a line (called an edge) if the ranges overlap, imagine the channels as colors assigned to the nodes, and voila! The phone companies are trying to solve a graph coloring problem.

Unfortunately, the graph coloring problem is nearly impossible to answer in full generality. 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.”

The mathematicians started their analysis with a simple observation: suppose there is a group of nodes in which every node is connected to every other one. Then every node in that group will need to be a different color. That 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. (Technically, there’s one more requirement for perfection: If you knock any number of nodes out of the graph along with all the edges that connect to those nodes, the clique number must remain sufficient to color the new graph.)

Easy to say, but which graphs are perfect?

This puzzle is one graph theorists have worried on for decades. They started their puzzling by looking for the “flaws” that make some graphs imperfect. One imperfect graph is a ring with an odd number of nodes, at least five, with each node connected just to its nearest neighbors. In this “odd hole,” only two nodes form a clique, but three colors are needed to color it. Another way to have an imperfect graph is the reverse, an “odd anti-hole”: Take a ring with an odd number of nodes, at least five, and connect each node to every other except for its neighbors.

The late mathematician Claude Berge of CNRS in Paris noticed that every imperfect graph he could find contained one of these two flaws. Those must be the only ones, he guessed, and in 1960 he created the strong perfect graph conjecture, the claim that a graph with neither an odd hole nor an odd anti-hole is perfect.

But he couldn’t prove it. And for nearly 40 years, the matter rested there.

In 2006, the problem finally yielded its secrets, and 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,” says Gerard Cornuejols of Carnegie Mellon University and Universite d'Aix-Marseille, whose ideas the team built upon. To encourage work on the problem, he offered \$5,000 of his own money for a proof, which the team collected.

Even with the proof, Guthrie’s Pandora’s box hasn’t been shut. Many more kinds of graphs remain to be colored. Furthermore, now mathematicians are looking for algorithms to efficiently detect perfect graphs. Others are seeking methods to find the minimal coloring the strong perfect graph theorem has shown must exist. The problems go on and on and on …

Comment

Chudnovsky, M., et al. 2006. The strong perfect graph theorem. Annals of Math 164:51-229. [Go to].

Please alert Science News to any inappropriate posts by clicking the REPORT SPAM link within the post. Comments will be reviewed before posting.

• I got confused. How many colors does an average phone company map actually have to have?
Phil Grimm
Mar. 8, 2009 at 9:41am
• No Signal Pink, Emergency Only Orange, Call Lost Green, Battery Low Blue
John Turner
Mar. 9, 2009 at 1:05pm
• I have the feeling that the problem is wrong. The wrongness of the problem is in the word "Country". The map is 2 dimensional in a part of the 3 dimensional word. I think it will be better to create a computer simulation that will test if there isn't the necessity, of a 5-th color which positive answer will close the problem. I have the filling that in a good created model, the 5-th color will be needed in a 2-dimensional world too.
Nikolay Minchev
Mar. 15, 2009 at 3:28pm
• "Despite the counties’ meandering shapes and varied configurations, four colors were all he needed to shade the map so that any two bordering counties were different colors. Perhaps, he speculated, four colors were enough for any map."

Imagine a map where every county was a hexagon. Every county would touch 6 other counties, and this map would, at a minimum, require 7 colors so that any two bordering counties were different colors.

"It took mathematicians nearly a century and a quarter to prove him right"

It took me two seconds to prove the statement in this article wrong.
Bob Smith
Mar. 19, 2009 at 1:13pm
• Sorry Bob, but you are the one in error. To need seven colors requires not only that each country touches six others, but that each of those countries touch the same of those other six, which does not occur. You have cliques of three, and you require three colors.
Colin Day
Mar. 19, 2009 at 8:42pm
• @Bob
Took me 3 seconds to read your comment, and took me a LONG time to finish laughing.
This country needs to catch up in Math&Sciences. No wonder the Asians and the European are laughing at us...
Ka C
Mar. 20, 2009 at 3:40pm
• The answer is different for maps drawn on the surface of a torus (one hole). How many colors are required at maximum in that case? Is there a general equation for torii of greater numbers of holes?
R Newsom
Apr. 1, 2009 at 10:03am
• This problem was solved over 30 years ago - see [Link was removed] for details.
Margaret Menzin
Apr. 8, 2009 at 10:24am
• Holy crap Bob - are you out of your element lol! This isn't facebook, man. I have to assume you're just pullin' our legs right haha!
KD Steiner
May. 5, 2009 at 10:22pm
• Bob,
You are wrong, It took my high school math class around one second to prove you wrong. If you draw the hexagons and color the middle one red, you can alternate different colors around the edges. then just repeat.
... Nice Try.
Victor Zampetti
Jun. 10, 2009 at 10:45am
• A 5-spoke wheel graph has a clique number of three and a
4-coloring. It is an imperfect graph with no apparent
hole.

Bill J.
bill jones
Jul. 16, 2009 at 4:03pm
• A fully "triangulated" planar
(FTP) graph does not have any
holes. Therefore it is "perfect"!
A FTP graph has a clique number
of 4 and by definition must be
4-colorable.
bill jones
Jul. 16, 2009 at 4:13pm
Oct. 16, 2009 at 9:35pm
• Face Lift Houston, Plastic Surgeon Dr. Siegel specializes in the Executive Facelift - back to work in 24 hours, natural looking and long lasting.
manish singh
Oct. 19, 2009 at 3:30am
• @Bob Smith
I see many others have pointed it out... but!

A series of counties in hexagonal pattern requires only three colors. The same is true of pentagon patterns.

@Fabi Jabr.. Thanks for the link!
Seoul_Dan
Oct. 25, 2009 at 7:17am
• I miss M.T. Will it be revived?
j netter
Oct. 29, 2009 at 12:59pm
• I also hope that this column is revived. I was sorry to see mathematics almost completely removed from the print issues, but these very nice articles made up for it.
tricycle222
Dec. 3, 2009 at 12:40am

sokaklar sokak
Jan. 5, 2010 at 5:35am

m9bnat m9bnat2
Jan. 14, 2010 at 10:44am
• hımm [Link was removed] Thank you very nice stories
Manga İndir
Jan. 15, 2010 at 10:42am
• "How many colors, mathematicians wondered, would it take to color any graph so that connected dots are always different colors?"

Since "any graph" could contain a clique of unbounded size, there is no limit to the number of colors that might be required in this completely general case. Maybe the author of this piece was trying to write something like the following:

"How many colors, mathematicians wondered, would it take to color graphs of various kinds so that connected dots are always different colors?"
Ralph Dratman
Jun. 29, 2010 at 1:23am
• ha-ha-ha! it is very simple problem and I do not see any reason to use computer. For some maps even 3 colors is enough- if all borders are even number (2,4,122 etc.). If odd number 4 colors enough. Very easy to prove it. Last time mathematics is too complicated)
Anton Sosinsky
Mar. 21, 2012 at 12:14pm