Well-colored graph

In graph theory, a subfield of mathematics, a well-colored graph is an undirected graph for which greedy coloring uses the same number of colors regardless of the order in which colors are chosen for its vertices.

The simplest example of a graph that is not well-colored is a four-vertex path.

Because there exists a non-optimal vertex ordering, the path is not well-colored.

Therefore, recognizing non-well-colored graphs can be performed within the complexity class NP.

Therefore, by a reduction from the Grundy number problem, it is NP-complete to test whether these two orderings exist.