An interval graph is an intersection graph of real intervals, that is, an undirected graph whose vertices can be labeled with real intervals so that there is an edge between two vertices iff their intervals intersect.
A comparability graph is an undirected graph that connects elements that are comparable in some partial order, i.e., it is a graph whose edges can be oriented in such a way that the resulting binary relation is transitive and antisymmetric.
Given any interval graph, $G$, it is known that its complement is a comparability graph, and in particular, the comparability graph of an interval order, that is, a strict partial order on intervals where $[x,y] < [z,w]$ iff $y < z$. Our question asks in what cases the complement of a comparability graph is also a comparability graph for some order.
For example, consider the case where vertices are identified with intervals and an edge is drawn when one interval is a subset of another but shares no endpoints. This forms a comparability graph for the so-called "interval containment" order, and we know that its complement is also a comparability graph for a product order on $\mathbb{R}^2$.
So, our general question is: under what conditions is the complement of a comparability graph also a comparability graph? We have a more particular example in mind and that is when the comparability graph is that of an interval order (as defined above) for all intervals in a range from 1 to some given N. The complement of this graph is clearly an interval graph (since in the complement, intervals are connected if they intersect). And one can think of this as a "complete" interval graph as all intervals in a range are represented. The question is: is it also a comparability graph?
Is this a known fact? If so, where might I find it? Or maybe it is an open question?
