The greedy coloring algorithm, when applied to a given ordering of the vertices of a graph G, considers the vertices of the graph in sequence and assigns each vertex its first available color, the minimum excluded value for the set of colors used by its neighbors.
Different vertex orderings may lead this algorithm to use different numbers of colors.
More formally, a graph G is said to be perfectly orderable if there exists an ordering π of the vertices of G, such that every induced subgraph of G is optimally colored by the greedy algorithm using the subsequence of π induced by the vertices of the subgraph.
[3] Another class of perfectly orderable graphs is given by the graphs G such that, in every subset of five vertices from G, at least one of the five has a closed neighborhood that is a subset of (or equal to) the closed neighborhood of another of the five vertices.
Because cographs are the graphs with no four-vertex induced path, they cannot violate the path-ordering requirement on a perfect ordering.