Perfect Graphs

This is a final project for MATH 1230: Graph Theory.
References:
[1] Maria Chudnovsky*, Gérard Cornuéjols**, Xiao Liu†, Paul Seymour, and Kristina Vušković,
Recognizing berge graphs, Combinatorica 25 (2005), no. 2, 143-186.
[2] Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, The strong perfect graph
theorem, Annals of Mathematics 164 (2006), no. 1, 51-229.
[3] László Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics 2
(1972), no. 3, 253-267.
The code that generated the animations for this video (using manim) can be accessed at github.com/AlexDuchnowski/PerfectGraphs.
If you liked this video, we recommend the Numberphile video with Maria Chudnovsky explaining the strong perfect graph theorem: • Perfect Graphs - Numbe... .

[@alexduchnowski8581]

Erratum: At 5:37, we claim that only the top graphs have holes of length 5. In fact, the graph with a hole of length 9 also has a hole of length 5, in fact it has several, as well as a hole of length 7, though we use the hole of length 9 to show the generalization to larger holes.

[@elijahberegovsky8957]

Hey! A new maths channel! Cool video, guys! Are you going to specialize on graph theory (my beloved) or maths in general?

[@markraya958]

What a great video. I really hope you guys plan on doing more of these

[@korigamik]

This is great! Can you share the source code for this video?

[@elytrae]

can you givea programming video on how to make math visuals?

[@Luiz-rt8eo]

But will the procedure you described at the end of the video generate all perfect graphs of order n? If i, for example, create an algorithm that adds all choices in a queue (add a isolated vertex or a dominating vertex) and executes them until I have added n vertices the queue is empty, will that generate all possible perfect graphs or size n?

[@gomorycut2000]

No, it will not generate all perfect graphs. They mention that this process will make a threshold graph (and that is all that it makes) and threshold graphs are a very small subset of perfect graphs. You can change that iterative process to something a bit more interesting: add a vertex and only attack it to an existing clique of any size... this will create a chordal graph - another subclass of perfect graphs. There are many other such iterative processes for other subclasses of perfect graphs.