Perfectly orderable graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

Definition[edit]

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. Different vertex orderings will lead this algorithm to use different numbers of colorings; there is always an ordering that leads to an optimal coloring (for instance, the ordering determined from an optimal coloring by sorting the vertices by their color has this property) but it may be difficult to find. The perfectly orderable graphs are defined to be the graphs for which there is an ordering that is optimal for the greedy algorithm not just for the graph itself, but for all of its induced subgraphs.

More formally, a graph G is said to be perfectly orderable if there exists an ordering π of the vertices of G, such that any induced subgraph is optimally colored by the greedy algorithm using the subsequence of π induced by the vertices of the subgraph. An ordering π has this property exactly when there do not exist four vertices a, b, c, and d for which abcd is an induced path, a appears before b in the ordering, and c appears after d in the ordering.[1]

Computational complexity[edit]

Perfectly orderable graphs are NP-complete to recognize.[2] However, it is easy to test whether a particular ordering is a perfect ordering of a graph. Consequentially, it is also NP-hard to find a perfect ordering of a graph, even if the graph is already known to be perfectly orderable.

Related graph classes[edit]

Every perfectly orderable graph is a perfect graph.[1]

Chordal graphs are perfectly orderable; a perfect ordering of a chordal graph may be found by reversing a perfect elimination ordering for the graph. Thus, applying greedy coloring to a perfect ordering provides an efficient algorithm for optimally coloring chordal graphs. Comparability graphs are also perfectly orderable, with a perfect ordering being given by a topological ordering of a transitive orientation of the graph.[1]

A concept intermediate between the perfect elimination ordering of a chordal graph and a perfect ordering is a semiperfect elimination ordering: in an elimination ordering, there is no three-vertex induced path in which the middle vertex is the first of the three to be eliminated, and in a semiperfect elimination ordering, there is no four-vertex induced path in which one of the two middle vertices is the first to be eliminated. The reverse of this ordering therefore satisfies the requirements of a perfect ordering, so graphs with semiperfect elimination orderings are perfectly orderable.[3] In particular, the same lexicographic breadth-first search algorithm used to find perfect elimination orders of chordal graphs can be used to find semiperfect elimination orders of distance-hereditary graphs, which are therefore also perfectly orderable.[4]

Several additional classes of perfectly orderable graphs are known.[5]

Notes[edit]

References[edit]