All variations on perfectly orderable graphs
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.
- Locally perfect graphs
- All variations on perfectly orderable graphs
- Welsh-Powell opposition graphs
- Opposition graphs are strict quasi-parity graphs
- A note on perfect orders
- Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs)
- A note on perfectly orderable graphs
- Forbidden induced subgraphs
- Classes of perfect graphs
- On opposition graphs, coalition graphs, and bipartite permutation graphs
- Perfectly orderable P₄ composition
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- Characterization and recognition of some opposition and coalition graph classes
- A note on strong perfectness of graphs
- scientific article; zbMATH DE number 4045795 (Why is no real title available?)
- On a conjecture of Hoàng and Tu concerning perfectly orderable graphs
- Bipolarizable graphs
This page was built for publication: All variations on perfectly orderable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114703)
