Are comparability graphs closed under vertex identification?

84 Views Asked by At

Are comparability graphs closed under edge contractions?

https://en.wikipedia.org/wiki/Comparability_graph

https://en.wikipedia.org/wiki/Edge_contraction#Vertex_identification

It seems like they are, since any function identifying vertices would correspond to a monotone map between two orientations.

1

There are 1 best solutions below

6
On BEST ANSWER

It's unclear whether you're asking about edge contractions or about all vertex identifications (your title and your question disagree) but the answer for both of them is no.

A cycle of length $6$ is a comparability graph, for example for the poset with elements $\{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}$ ordered by inclusion, as shown below.

enter image description here

If you contract any edge, you get a cycle of length $5$, which is not a comparability graph because it's not perfect.

Or, for a self-contained demonstration: suppose that $C_5$ were a comparability graph. Orient each edge $vw$ to point in the direction $v \to w$ when $v < w$. Because the cycle is odd, the edges cannot alternate direction all the way around the cycle: there must be two consecutive edges $uv, vw$ oriented $u \to v, v \to w$ or $u \gets v, v \gets w$. But now, transitivity demands that the edge $uw$ should also exist, and it doesn't: contradiction!