<p>perfect graphs were first motivated by information transmission theory originating with Shannon ie <a href="http://mathworld.wolfram.com/ShannonCapacity.html">Shannon Capacity of graphs</a>. 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.</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>[1] C. Berge, The history of the perfect graphs, Southeast Asian Bull. Math.
20, No.1 (1996) 5-10.<br>
[2] C. Berge, Motivations and history of some of my conjectures, Discrete Mathematics
165-166 (1997) 61-70.<br>
[3] <a href="http://rads.stackoverflow.com/amzn/click/0471489700">Perfect Graphs</a> by Jorge L. Ramírez-Alfonsín (Editor), Bruce A. Reed (Editor), J.L.R. Alfonsin (Author). Wiley. Ch1, Origins and Genesis by Berge &amp; Ramírez-Alfonsín</p>

CC BY-SA 3.0
2012-11-21T18:13:33.617Z
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](http://en.wikipedia.org/wiki/Lovász_number) 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 
CC BY-SA 3.0
2018-01-10T21:19:05.107Z
I like the succinctness of the answer, in conjunction with the citations.  This is a topic on the periphery for me, and this short answer is quite useful as an intro to a complex subject.
DukeZhou
CC BY-SA 3.0
2012-11-21T16:16:23.693Z
2012-11-21T17:13:34.420Z
2012-11-21T17:13:34.420Z
vzn
<p>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. <a href="http://en.wikipedia.org/wiki/Perfect_graph">Perfect graphs</a> have many beautiful properties, but what is the single reason they are called perfect? Or is it just a aesthetic preference by Berge?</p>

CC BY-SA 3.0
2012-11-21T12:30:33.220Z
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 
CC BY-SA 3.0
2012-11-21T12:49:21.763Z
The meaning is exactly the same in our language as in yours.
Anthony Labarre
<graph-theory><co.combinatorics><terminology><graph-colouring>
Why are perfect graphs called perfect?
Arindam Pal
# Why are perfect graphs called perfect?

(Asked by: username_0 on 2012-11-21)

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](http://en.wikipedia.org/wiki/Perfect_graph) have many beautiful properties, but what is the single reason they are called perfect? Or is it just a aesthetic preference by Berge?

**Tags:** graph-theory, co.combinatorics, terminology, graph-colouring
> **Comments:**
> **username_1**: 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.  
> **username_2**: The meaning is exactly the same in our language as in yours.  

---

## 1 answers

### Answer by username_3 on 2012-11-21. Score: 17 | Accepted answer

perfect graphs were first motivated by information transmission theory originating with Shannon ie [Shannon Capacity of graphs](http://mathworld.wolfram.com/ShannonCapacity.html). 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](http://rads.stackoverflow.com/amzn/click/0471489700) 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

> **Comments:**
> **username_1**: 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](http://en.wikipedia.org/wiki/Lovász_number) 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.  
> **username_4**: I like the succinctness of the answer, in conjunction with the citations.  This is a topic on the periphery for me, and this short answer is quite useful as an intro to a complex subject.  

---

