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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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. $\endgroup$– Peter ShorNov 21, 2012 at 12:30
-
6$\begingroup$ The meaning is exactly the same in our language as in yours. $\endgroup$– Anthony LabarreNov 21, 2012 at 12:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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
-
11$\begingroup$ 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. $\endgroup$ Nov 21, 2012 at 18:13
-
$\begingroup$ 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. $\endgroup$– DukeZhouJan 10, 2018 at 21:19