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

CC BY-SA 3.0
2012-12-03T18:57:00.870Z
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
CC BY-SA 3.0
2014-02-19T18:34:56.980Z
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.
JimN
CC BY-SA 3.0
2011-08-09T14:26:30.353Z
2011-08-09T14:26:30.353Z
Stefan Kratsch
<p>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.</p>

<p>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).</p>

CC BY-SA 3.0
2014-04-03T11:51:53.197Z
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
CC BY-SA 4.0
2020-04-21T19:41:38.747Z
The translation of Gallai's paper by Frederic Maffray and Myriam Preissmann is Chapter 3 of *Perfect Graphs* by Jorge L. Ramirez Alfonsin and Bruce A. Reed (eds.), Wiley, 2001, pages 25-66.
Timothy Chow
CC BY-SA 4.0
2020-04-24T15:30:23.200Z
The list in Trotter's book is wrong. You can get the forbidden subgraphs by combining "TAFEL I" and "TAFEL II" in Gallai's paper, except that TAFEL I shows the *knotting graphs* of the graphs of interest (so you should merge the vertices that are drawn close together to get the actual graph) and TAFEL II contains the *complements* of the graphs of interest. Trotter forgot to complement the graphs in TAFEL II.
Timothy Chow
CC BY-SA 3.0
2012-12-03T11:29:24.377Z
2012-12-03T11:43:31.783Z
2012-12-03T11:43:31.783Z
Anthony Labarre
<p>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".</p>

<p>Thank you for your help in advance. :-)</p>

<graph-theory><co.combinatorics>
Is there a list of forbidden subgraphs for comparability graphs?
Peng Zhang
# Is there a list of forbidden subgraphs for comparability graphs?

(Asked by: username_0 on 2011-08-09)

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. :-)

**Tags:** graph-theory, co.combinatorics

---

## 2 answers

### Answer by username_1 on 2011-08-09. Score: 9

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)

> **Comments:**
> **username_2**: 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.  
> **username_3**: 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.  

---

### Answer by username_4 on 2012-12-03. Score: 4

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).

> **Comments:**
> **username_5**: 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..)  
> **username_6**: The translation of Gallai's paper by Frederic Maffray and Myriam Preissmann is Chapter 3 of *Perfect Graphs* by Jorge L. Ramirez Alfonsin and Bruce A. Reed (eds.), Wiley, 2001, pages 25-66.  
> **username_6**: The list in Trotter's book is wrong. You can get the forbidden subgraphs by combining "TAFEL I" and "TAFEL II" in Gallai's paper, except that TAFEL I shows the *knotting graphs* of the graphs of interest (so you should merge the vertices that are drawn close together to get the actual graph) and TAFEL II contains the *complements* of the graphs of interest. Trotter forgot to complement the graphs in TAFEL II.  

---

