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 and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

Different choices of the sequence of vertices will typically produce different colorings of the given graph, so much of the study of greedy colorings has concerned how to find a good ordering. There always exists an ordering that produces an optimal coloring, but although such orderings can be found for many special classes of graphs, they are hard to find in general. Commonly used strategies for vertex ordering involve placing higher-degree vertices earlier than lower-degree vertices, or choosing vertices with fewer available colors in preference to vertices that are less constrained.

Variations of greedy coloring choose the colors in an online manner, without any knowledge of the structure of the uncolored part of the graph, or choose other colors than the first available in order to reduce the total number of colors. Greedy coloring algorithms have been applied to scheduling and register allocation problems, the analysis of combinatorial games, and the proofs of other mathematical results including Brooks' theorem on the relation between coloring and degree. Other concepts in graph theory derived from greedy colorings include the Grundy number of a graph (the largest number of colors that can be found by a greedy coloring), and the well-colored graphs, graphs for which all greedy colorings use the same number of colors.

The greedy coloring for a given vertex ordering can be computed by an algorithm that runs in linear time. The algorithm processes the vertices in the given ordering, assigning a color to each one as it is processed. The colors may be represented by the numbers ${\displaystyle 0,1,2,\dots }$ and each vertex is given the color with the smallest number that is not already used by one of its neighbors. To find the smallest available color, one may use an array to count the number of neighbors of each color (or alternatively, to represent the set of colors of neighbors), and then scan the array to find the index of its first zero.

In Python, the algorithm can be expressed as:

The first_available subroutine takes time proportional to the length of its argument list, because it performs two loops, one over the list itself and one over a list of counts that has the same length. The time for the overall coloring algorithm is dominated by the calls to this subroutine. Each edge in the graph contributes to only one of these calls, the one for the endpoint of the edge that is later in the vertex ordering. Therefore, the sum of the lengths of the argument lists to first_available, and the total time for the algorithm, are proportional to the number of edges in the graph.

An alternative algorithm, producing the same coloring, is to choose the sets of vertices with each color, one color at a time. In this method, each color class ${\displaystyle C}$ is chosen by scanning through the vertices in the given ordering. When this scan encounters an uncolored vertex ${\displaystyle v}$ that has no neighbor in ${\displaystyle C}$, it adds ${\displaystyle v}$ to ${\displaystyle C}$. In this way, ${\displaystyle C}$ becomes a maximal independent set among the vertices that were not already assigned smaller colors. The algorithm repeatedly finds color classes in this way until all vertices are colored. However, it involves making multiple scans of the graph, one scan for each color class, instead of the method outlined above which uses only a single scan.

Different orderings of the vertices of a graph may cause the greedy coloring to use different numbers of colors, ranging from the optimal number of colors to, in some cases, a number of colors that is proportional to the number of vertices in the graph. For instance, a crown graph (a graph formed from two disjoint sets of n/2 vertices {a₁, a₂, ...} and {b₁, b₂, ...} by connecting a_i to b_j whenever i ≠ j) can be a particularly bad case for greedy coloring. With the vertex ordering a₁, b₁, a₂, b₂, ..., a greedy coloring will use n/2 colors, one color for each pair (a_i, b_i). However, the optimal number of colors for this graph is two, one color for the vertices a_i and another for the vertices b_i. 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.