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
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityI 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
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.