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.
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?
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.
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.
What a great video. I really hope you guys plan on doing more of these
Hey! A new maths channel! Cool video, guys! Are you going to specialize on graph theory (my beloved) or maths in general?
can you givea programming video on how to make math visuals?
This is great! Can you share the source code for this video?
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?
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.