Let $X$ be a finite set equipped with a partial order. (Not a preorder: $a < b$ implies $b \not< a$.) The corresponding incomparability graph has vertex set $X$ with an edge between two points iff they are incomparable.

I am interested in posets for which the incomparability graph is connected and are maximal for this property. That is, making any pair of incomparable elements comparable disconnects the incomparability graph.

Is there any hope of classifying such partial orders? For example, the set $\{a_1, \ldots, a_{n-1},b\}$ with $a_i < a_j$ when $i < j$ and $b$ incomparable to each $a_i$ is maximal in the desired sense. (If we make $b$ comparable to some $a_i$ then this $a_i$ will be comparable to everything and hence an isolated point.) But there are other examples that don't look like this.


It is possible to classify the trees that are incomparability graphs (also called co-comparability graphs) as caterpillars.

Minimal connected graph is a tree, and a co-comparability graph does not contain a subdivided $K_{1,3}$ as an induced subgraph; it is denoted by $T_2$ on http://www.graphclasses.org/classes/gc_147.html.

Trees with no induced $T_2$ are caterpillars (https://en.wikipedia.org/wiki/Caterpillar_tree), and it is easy to see that every caterpillar can be represented as an intersection graph of $x$-monotone curves between two vertical lines; in fact, it is a permutation graph (and therefore co-comparability graph).

The next step would be to show that minimal connected incomparability graphs are trees. It might be helpful to use the representation of incomparability graphs as intersection graphs of x-monotone curves between two vertical lines; this can also help with characterizing the posets, since the order in the poset corresponds to vertical orderning of disjoint curves in the representation.

  • $\begingroup$ From your link it looks like any subgraph of a co-comparability graph is also a co-comparability graph. Is that right? (Otherwise I wonder if a minimal connected co-comparability graph must be a minimal connected graph.) $\endgroup$ – Nik Weaver Dec 11 '18 at 14:58
  • $\begingroup$ Your answer is very helpful --- thank you --- but it doesn't directly solve my problem since I wanted to know what are the maximal posets. It isn't even clear to me that given a maximal poset with connected co-comparability graph, that graph has to be a minimal connected co-comparability graph ... $\endgroup$ – Nik Weaver Dec 11 '18 at 14:59
  • $\begingroup$ @Nik Weaver A subgraph of a co-comparability graph does not have to be a co-comparability graph: for example, all complete graphs are co-comparability graphs, but not all graphs are co-comparability graphs. But you are right that it is missing to show that minimal connected co-comparability graphs are indeed trees. $\endgroup$ – Jan Kyncl Dec 11 '18 at 19:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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