graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a

greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence a ...

algorithm with that ordering optimally colors every

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definit ...

of the given graph. Perfectly orderable graphs form a special case of the

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph ( clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is per ...

s, and they include the

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...

comparability graph In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graph ...

s, and

distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any ...

s. However, testing whether a graph is perfectly orderable is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

Definition

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. There is always an ordering that leads to an optimal coloring – this is true, for instance, of the ordering determined from an optimal coloring by sorting the vertices by their color – 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

s. More formally, a graph ''G'' is said to be ''perfectly orderable'' if there exists an ordering π of the vertices of ''G'', such that every

of ''G'' 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.; .

Computational complexity

Perfectly orderable graphs are NP-complete to recognize. However, it is easy to test whether a particular ordering is a perfect ordering of a graph. Consequently, 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

Every perfectly orderable graph is a

Chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...

s 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 graph In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graph ...

s are also perfectly orderable, with a perfect ordering being given by a

topological ordering In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge ''uv'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For ins ...

of a

transitive orientation Transitivity or transitive may refer to: Grammar * Transitivity (grammar), a property of verbs that relates to whether a verb can take direct objects * Transitive verb, a verb which takes an object * Transitive case In linguistic typology, transi ...

of the graph. The

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement ...

s of tolerance graphs are perfectly orderable. 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. Equivalently, these are the graphs in which the

partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...

of closed neighborhoods, ordered by set inclusion, has

width Length is a measure of distance. In the International System of Quantities, length is a quantity with dimension distance. In most systems of measurement a base unit for length is chosen, from which all other units are derived. In the Inter ...

at most four. The 5-vertex

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

has a neighborhood partial order of width five, so four is the maximum width that ensures perfect orderability. As with the chordal graphs (and unlike the perfectly orderable graphs more generally) the graphs with width four are recognizable in polynomial time. 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 the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...

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. In particular, the same

lexicographic breadth-first search In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth ...

algorithm used to find perfect elimination orders of chordal graphs can be used to find semiperfect elimination orders of

s, which are therefore also perfectly orderable. The graphs for which every vertex ordering is a perfect ordering are the

cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

s. Because cographs are the graphs with no four-vertex induced path, they cannot violate the path-ordering requirement on a perfect ordering. Several additional classes of perfectly orderable graphs are known.; ; ; ; , pp. 81–86.

Notes

References

* * *. As cited by . *. *. As cited by . *. * *. *. *. *. *{{citation , last = Payan , first = Charles , doi = 10.1016/0012-365X(83)90064-X , issue = 2 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continu ...

, mr = 689816 , pages = 229–230 , title = Perfectness and Dilworth number , volume = 44 , year = 1983, doi-access = free . Graph coloring Perfect graphs