A graph is perfectly orderable if it admits a perfect ordering. He proved that an ordering is perfect if and only if it contains no obstruction, and that all perfectly orderable graphs are perfect. Since each induced subgraph of a strongly orderable graph is again strongly orderable, the class of strongly orderable graphs is perfect. Meyniel graph 1.
Graph coloring is in general a hard problem.
As such, it is interesting to investigate restrictions under which a graph s chromatic number might be easily determined. Having introduced a new class of graphs, it is natural to ask how the class relates to other previously studied classes of graphs. Before explaining their results, we present some motivating background material. Perfect orders and doubly lexical orders. A class of graphs that is closely related to the perfect graphs is the t perfect graphs.