MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

One source I found over the Internet is Information System on Graph Classes and their Inclusions. There you can find a page devoted to comparability graphs, complements of comperability graphs (a.k.a (XF12n+3,XF52n+3,XF62n+2,Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,co-XF2n+1,co-XF3n,co-XF4n,odd-hole)-free graphs), and graphs which are comparability $\cap$ co-comparability. This class coincides with six other classes which are equivalent but are defined differently.

Overall, it looks that it is best to consider the above classes of graphs in terms of forbidden induced subgraphs.

share|cite|improve this answer
Anf if you happen to want to recognise permutation graphs on a computer, here's what you need :… :-) – Nathann Cohen Jul 25 '13 at 8:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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