Revision as of 02:18, 22 July 2010 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,834 edits →Relation to other graph families: trivially perfect ← Previous edit		Revision as of 02:18, 22 July 2010 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,834 edits m →Relation to other graph families: typo Next edit →
Line 23: A [[permutation graph]] is a containment graph on a set of intervals.<ref>{{harvtxt\|Dushnik\|Miller\|1941}}. {{harvtxt\|Brandstädt\|Le\|Spinrad\|1999}}, theorem 6.3.1, p. 95.</ref> Therefore, permutation graphs are another subclass of comparability graphs. The [[trivially ~~prefect~~perfect graph]]s are the comparability graphs of [[rooted tree]]s.<ref>{{harvtxt\|Brandstädt\|Le\|Spinrad\|1999}}, theorem 6.6.1, p. 99.</ref> [[Cograph]]s can be characterized as the comparability graphs of [[series-parallel partial order]]s; thus, cographs are also comparability graphs.<ref>{{harvtxt\|Brandstädt\|Le\|Spinrad\|1999}}, corollary 6.4.1, p. 96; {{harvtxt\|Jung\|1978}}.</ref>

Comparability graph: Difference between revisions