0
$\begingroup$

Let $G=(V,E)$ be a simple, undirected graph. Is there a partial ordering $\leq\subseteq (V\times V)$ with the following property? $$\{v,w\} \in E \text{ if and only if } v||y$$

(We write $v||w$ in the poset $(V,\leq)$ if $v\not \leq w$ and $w\not\leq v$?)

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$

Any incomparability graph is perfect (shown by Dilworth in 1950), so any non-perfect graph will be a counterexample. For an explicit counterexample, choose the cycle on $5$ vertices.

Improve this answer
$\endgroup$
6
$\begingroup$

No and they are called incomparability graphs: https://en.wikipedia.org/wiki/Comparability_graph

Improve this answer
$\endgroup$
2
$\begingroup$

Well, if you look at the complement, you have a "comparability" graph, in which every chain of the poset corresponds to a clique. It is enough to see that is a very particular class.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .