1
$\begingroup$

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

$\endgroup$
1

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.