1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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
    Commented May 26, 2011 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
    Commented May 27, 2011 at 1:00
  • $\begingroup$ I have understood that the Description by Andras Frank. $\endgroup$
    – Haoran Wang
    Commented Jun 20, 2011 at 4:11

2 Answers 2

Reset to default
3
$\begingroup$

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'.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jun 20, 2011 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
    Commented Jun 21, 2011 at 1:48
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link is broken now. $\endgroup$
    – Petr Hudeček
    Commented Feb 3, 2014 at 13:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .