Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is the single reason they are called perfect? Or is it just a aesthetic preference by Berge?

share|cite|improve this question
Presumably, he originally called them parfait and not perfect. It does mean almost the same thing. Possibly some French speaker here could tell us whether parfait in French is slightly less absolute in meaning than perfect in English. – Peter Shor Nov 21 '12 at 12:30
The meaning is exactly the same in our language as in yours. – Anthony Labarre Nov 21 '12 at 12:49
up vote 14 down vote accepted

perfect graphs were first motivated by information transmission theory originating with Shannon ie Shannon Capacity of graphs. they are called "perfect" by Berge because they can be used to model a noiseless or "perfect" information channel wrt transposition errors in transmission called "confounding". from intro in [3] which also has a very detailed history in the 1st chapter cowritten by Berge.

When Claude Berge defined perfect graphs in 1961, he was motivated by a very practical problem: how do we maximize the rate at which information is sent through a (noisy) transmission channel while avoiding the introduction of errors because of the physical imperfections of the system?

[1] C. Berge, The history of the perfect graphs, Southeast Asian Bull. Math. 20, No.1 (1996) 5-10.
[2] C. Berge, Motivations and history of some of my conjectures, Discrete Mathematics 165-166 (1997) 61-70.
[3] Perfect Graphs by Jorge L. Ramírez-Alfonsín (Editor), Bruce A. Reed (Editor), J.L.R. Alfonsin (Author). Wiley. Ch1, Origins and Genesis by Berge & Ramírez-Alfonsín

share|cite|improve this answer
I suspect this answer could use more explanation. For perfect graphs, the single-symbol zero-error capacity (encoding the information without using block codes) is equal to the asymptotic zero-error capacity. Thus, you can easily calculate the zero-error capacity, and it is obtainable using the simplest possible code. One of Lovász's celebrated results was calculating this capacity for the five-cycle, the simplest non-perfect graph. And unless progress has been made in the last couple of years, we still don't know what it is for the seven-cycle. – Peter Shor Nov 21 '12 at 18:13
Thanks to both vzn and Peter for your answers. – Arindam Pal Nov 23 '12 at 6:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.