All variations on perfectly orderable graphs (Q1114703)

An ordered graph is a graph whose vertices are positive integers. Two ordered graphs are isomorphic if there exists an order preserving bijection between their sets of vertices which is a graph isomorphism. A graph G is perfect if each of G's induced subgraphs has chromatic number equal the number of vertices in its largest clique. The author identifies the family of all sets S of ordered graphs with the following properties: (1) each member of S is a path with 4 vertices. (2) If an ordered graph Z has no induced subgraph isomorphic to a member of S then Z is perfect. This work is related to Berge's strong perfect graph. Conjecture: Graph G is perfect iff no induced subgraph of G or \(\bar G\) is an odd cycle of length at least 5.