I am currently trying to learn in depth different concepts in graph theory. I can not quite understand what the difference is between Perfectly orderable graph and Perfect Elimination Ordering?
I would be happy to help with this. Thanks
$\begingroup$
$\endgroup$
1
-
$\begingroup$ en.wikipedia.org/wiki/Chordal_graph en.wikipedia.org/wiki/Perfectly_orderable_graph $\endgroup$– Om3gaMay 10, 2021 at 10:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A perfectly orderable graph is a graph which has a perfect ordering.
A vertex order $<$ of $G$ is perfect if and only if $G$ contains no $P_4$ $abcd$ with $a < b$ and $d < c$.
A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex $v,$ $v$ and the neighbors of $v$ that occur after $v$ in the order form a clique. Explained/simpler definition.
