Welcome to MathOverflow

Question

1

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.

edited Jun 20 2011 at 5:27

asked May 26 2011 at 8:17

Haoran Wang
11●2

	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. – Abel Stolz May 26 2011 at 9:27
	Hi, Abel. Do you know how to use the relication lemma to prove the weak perfect graph theorem? – Haoran Wang May 27 2011 at 1:00
	I have understood that the Description by Andras Frank. – Haoran Wang Jun 20 2011 at 4:11

Andrew D. King · Answer 1 · 2011-06-13 12:32:22Z UTC

2

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.columbia.edu/~ak3074/papers/phdthesis-compact.pdf

answered Jun 13 2011 at 12:32

Andrew D. King
1,087●6●11

5

Corrupted PDF file? – darij grinberg Jun 13 2011 at 13:40

Thank you and sorry! It seems to be fixed now. – Andrew D. King Jun 13 2011 at 16:14

Tony Huynh · Answer 2 · 2011-06-13 15:49:25Z UTC

2

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

edited Jun 13 2011 at 15:49

answered Jun 13 2011 at 14:52

Tony Huynh
9,023●1●22●62

	Thanks a lot for that! – Haoran Wang Jun 18 2011 at 2:17
	You're welcome. If you feel that this answers your question, then you can click on the green checkmark to indicate so. – Tony Huynh Jun 20 2011 at 10:10
	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. – Haoran Wang Jun 21 2011 at 1:48

Combinatorial Proof of Weak Perfect Graph Theorem.

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.