In the study of graph coloring

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...

 problems in mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 and computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a greedy coloring is a coloring of the vertices

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

 of a graph formed by a greedy algorithm

Greedy algorithm

A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....

 that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings do not in general use the minimum number of colors possible; however they have been used in mathematics as a technique for proving other results about colorings and in computer science as a heuristic to find colorings with few colors.

The perfectly orderable graphs, defined by the optimality of the greedy algorithm on their induced subgraphs, form an important subclass of perfect graph

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....

s.

Vertex ordering

A crown graph

Crown graph

In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j...

 (a complete bipartite graph

Complete bipartite graph

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...

 K_n,n, with the edges of a perfect matching removed) is a particularly bad case for greedy coloring: if the vertex ordering places two vertices consecutively whenever they belong to one of the pairs of the removed matching, then a greedy coloring will use n colors, while the optimal number of colors for this graph is two. There also exist graphs such that with high probability a randomly chosen vertex ordering leads to a number of colors much larger than the minimum. Therefore, it is of some importance in greedy coloring to choose the vertex ordering carefully.

The vertices of any graph may always be ordered in such a way that the greedy algorithm produces an optimal coloring. For, given any optimal coloring in which the smallest color set is maximal, the second color set is maximal with respect to the first color set, etc., one may order the vertices by their colors. Then when one uses a greedy algorithm with this order, the resulting coloring is automatically optimal. However, due to the NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

ness of the graph coloring problem, it is difficult to find an ordering that leads to a minimum number of colors. For this reason, heuristics have been used that attempt to reduce the number of colors while not guaranteeing an optimal number of colors.

A commonly used ordering for greedy coloring is to choose a vertex v of minimum degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...

, order the remaining vertices, and then place v last in the ordering. If every subgraph of a graph G contains a vertex of degree at most d, then the greedy coloring for this ordering will use at most d + 1 colors. The smallest such d is commonly known as the degeneracy

Degeneracy (graph theory)

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate...

 of the graph.

For a graph of maximum degree Δ, any greedy coloring will use at most Δ + 1 colors. Brooks' theorem states that with two exceptions (cliques

Complete graph

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

 and odd cycles

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 connected in a closed chain. The cycle graph with n vertices is called Cn...

) at most Δ colors are needed, and one proof of Brooks' theorem involves finding a vertex ordering in which the first two vertices are adjacent to the final vertex but not adjacent to each other, so that a greedy coloring for this ordering uses only Δ colors.

It is NP-complete to determine, for a given graph G and number k, whether some ordering of the vertices of G forces the greedy algorithm to use k or more colors. In particular, this means that it is difficult to find the worst ordering for G.

Alternative color selection schemes

It is possible to define a greedy coloring algorithm in which the vertices of the given graph are colored in a given sequence but in which the color chosen for each vertex is not necessarily the first available color; alternative color selection strategies have been studied within the framework of online algorithm

Online algorithm

In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...

s. In the online graph-coloring problem, vertices of a graph are presented one at a time in an arbitrary order to a coloring algorithm; the algorithm must choose a color for each vertex, based only on the colors of and adjacencies among already-processed vertices. In this context, one measures the quality of a color selection strategy by its competitive ratio

Competitive analysis (online algorithm)

Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance...

, the ratio between the number of colors it uses and the optimal number of colors for the given graph.

If no additional restrictions on the graph are given, the optimal competitive ratio is only slightly sublinear. However, for interval graph

Interval graph

In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...

s, a constant competitive ratio is possible, while for bipartite graph

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

s and sparse graphs a logarithmic ratio can be achieved. Indeed, for sparse graphs, the standard greedy coloring strategy of choosing the first available color achieves this competitive ratio, and it is possible to prove a matching lower bound on the competitive ratio of any online coloring algorithm.

Perfectly orderable graphs

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. That is, π must not only be an optimal ordering for the greedy algorithm for G, but for every induced subgraph of G. 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. Perfectly orderable graphs form a subset of the perfect graph

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....

s, but are NP-complete to recognize.

Chordal graph

Chordal graph

In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

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

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...

s are also perfectly orderable, with a perfect ordering being given by a topological ordering of a transitive orientation of the graph.

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. In particular, the same lexicographic breadth-first search

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, that is used as part of other graph algorithms such as the recognition of chordal graphs and optimal coloring of distance-hereditary graphs...

 algorithm used to find perfect elimination orders of chordal graphs can be used to find semiperfect elimination orders of distance-hereditary graph

Distance-hereditary graph

In graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...

s, which are therefore also perfectly orderable.

Several additional classes of perfectly orderable graphs are known.