Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

You could refer to the entry for comparability graphs on graphclasses.org: http://www.graphclasses.org/classes/gc_72.html (look at "equivalent classes" and note that the list is not finite)

share|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|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

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.