Skip to main content
MathOverflow

Return to Question

added 152 characters in body
Source Link
Haoran Wang
Haoran Wang
  • 11
  • 4

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.

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

fixed spelling in title
Link
Tony Huynh
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Combintorial Combinatorial Proof of Weak Perfect Graph theoryTheorem.

Source Link
Haoran Wang
Haoran Wang
  • 11
  • 4

Combintorial Proof of Weak Perfect Graph theory

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.