I am reading Andras Frank's Connections in Combinatorial Optimization. On the Page 34, the description of how to use the Replication Lemma to prove the weak perfect graph theorem seems only to prove that there must be a largest maximal stable set intersecting all largest cliques, if not, a contradiction occur. I think that there are some more steps are needed.

I have understood the proof in Frank's Connections in Combinatorial Optimization.It is interesting that how natural about the combinatorial proof.

  • $\begingroup$ So ist your question wether you are right or not, or what the missing steps are? Perhaps you could explain a bit, why you think that the proof is insufficient. $\endgroup$ – Abel Stolz May 26 '11 at 9:27
  • $\begingroup$ Hi, Abel. Do you know how to use the relication lemma to prove the weak perfect graph theorem? $\endgroup$ – Haoran Wang May 27 '11 at 1:00
  • $\begingroup$ I have understood that the Description by Andras Frank. $\endgroup$ – Haoran Wang Jun 20 '11 at 4:11

Lovász' original 1972 proof of the (weak) perfect graph theorem was completely combinatorial. The proof can be found in Diestel's book Graph Theory, which you can peruse for free online here. It is Theorem 5.5.4, and afterwards includes a nice explanation by Diestel why vertex replication is 'natural'.

  • $\begingroup$ You're welcome. If you feel that this answers your question, then you can click on the green checkmark to indicate so. $\endgroup$ – Tony Huynh Jun 20 '11 at 10:10
  • $\begingroup$ I will do that. In fact, I feel that the explanation by Andras Frank in his book is really really good and elegant. I am shame to say that just at first glance, I did not understood a key point. $\endgroup$ – Haoran Wang Jun 21 '11 at 1:48

I feel a bit guilty because this is the second time I have pointed someone to my thesis for fundamental material, but the proof of the WPGT via the Replication Lemma is in Section 3.2. http://www.sfu.ca/~adk7/papers/phdthesis-compact.pdf

  • $\begingroup$ The link is broken now. $\endgroup$ – Petr Hudeček Feb 3 '14 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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