3
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – András Salamon Dec 3 '12 at 18:57
  • 1
    $\begingroup$ 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. $\endgroup$ – JimN Feb 19 '14 at 18:34
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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..) $\endgroup$ – NisaiVloot Apr 3 '14 at 11:51
  • 1
    $\begingroup$ 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. $\endgroup$ – Timothy Chow Apr 21 at 19:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Timothy Chow Apr 24 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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