Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

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

The "graph classes: a survey" mentioned Trotter and other authors have presented a list of forbidden subgraph of comparability graph. But the google book( where I read graph classes: a survey) do not have the page which contains the reference of specific literature. To my knowledge, one forbidden graph is "a k-cycle ( k is an odd intege $\ge$ 5) and no triangle chord".

Thank you for your help in advance. :-)

share|cite|improve this question

You could refer to the entry for comparability graphs on (look at "equivalent classes" and note that the list is not finite)

share|cite|improve this answer
Although Stefan is right, the infinite part is simply "odd-hole-free". The list also has helpful links to pictures of all the other excluded graphs. – András Salamon Dec 3 '12 at 18:57
No, András, every one of those "n"s in the exponents of many of the forbidden configurations are arbitrary parameters ... each one of those XF^ symbols is an infinite family of graphs. Also, the subscript $n$ for co-holes is another infinite set of forbidden graphs. It's not only the odd holes. – Jim Nastos Feb 19 '14 at 18:34

You must be referring to page 91 of that book. The reference is T. GALLAI, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hung., 18 (1967), 25-66. A translation exists, but I was unable to find it online.

The list is apparently also available in W.T. TROTTER, JR., Combinatorics and Partially Ordered Sets — Dimension Theory, Johns Hopkins University Press, Baltimore, London (1992).

share|cite|improve this answer
The translation can be obtained from F. Maffray by an email request, that's how I got it myself. Be warned that the paper is a difficult read though (44p long, a number that doesn't bode well to me..) – NisaiVloot Apr 3 '14 at 11:51
The list in Trotter's book is wrong. It is supposed to be a list of forbidden subgraphs for comparability graphs but for example $C_6$ is in his list. The list looks more like the list of forbidden subgraphs for incomparability graphs, but I'm not sure it's that either. – Timothy Chow Nov 20 '15 at 21:18

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.