Hubbry Logo
Greedy coloringGreedy coloringMain
Open search
Greedy coloring
Community hub
Greedy coloring
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Greedy coloring
Greedy coloring
Greedy coloring
View on Wikipedia
from Wikipedia

Two greedy colorings of the same crown graph using different vertex orders. The right example generalises to 2-colorable graphs with n vertices, where the greedy algorithm expends n/2 colors.

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring[1] 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.

Algorithm

[edit]

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 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.[2]

In Python, the algorithm can be expressed as: 

def first_available(colors):
    """Return smallest non-negative integer not in the given set of colors.
    """
    color = 0
    while color in colors:
        color += 1
    return color

def greedy_coloring(G, order):
    """Find the greedy coloring of G in the given order.

    The representation of G is assumed to be like https://www.python.org/doc/essays/graphs/
    in allowing neighbors of a node/vertex to be iterated over by "for w in G[node]".
    The return value is a dictionary mapping vertices to their colors.
    """
    coloring = dict()
    for node in order:
        used_neighbour_colors = {coloring[nbr]
                                 for nbr in G[node]
                                 if nbr in coloring}
        coloring[node] = first_available(used_neighbour_colors)
    return coloring

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.[2]

An alternative algorithm, producing the same coloring,[3] is to choose the sets of vertices with each color, one color at a time. In this method, each color class is chosen by scanning through the vertices in the given ordering. When this scan encounters an uncolored vertex that has no neighbor in , it adds to . In this way, 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.[4]

Choice of ordering

[edit]

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 {a1, a2, ...} and {b1, b2, ...} by connecting ai to bj whenever i ≠ j) can be a particularly bad case for greedy coloring. With the vertex ordering a1, b1, a2, b2, ..., a greedy coloring will use n/2 colors, one color for each pair (ai, bi). However, the optimal number of colors for this graph is two, one color for the vertices ai and another for the vertices bi.[5] 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.[6] Therefore, it is of some importance in greedy coloring to choose the vertex ordering carefully.

Good orders

[edit]

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, one may order the vertices by their colors. Then when one uses a greedy algorithm with this order, the resulting coloring is automatically optimal.[7] However, because optimal graph coloring is NP-complete, any subproblem that would allow this problem to be solved quickly, including finding an optimal ordering for greedy coloring, is NP-hard.[8]

In interval graphs and chordal graphs, if the vertices are ordered in the reverse of a perfect elimination ordering, then the earlier neighbors of every vertex will form a clique. This property causes the greedy coloring to produce an optimal coloring, because it never uses more colors than are required for each of these cliques. An elimination ordering can be found in linear time, when it exists.[9]

More strongly, any perfect elimination ordering is hereditarily optimal, meaning that it is optimal both for the graph itself and for all of its induced subgraphs. The perfectly orderable graphs (which include chordal graphs, comparability graphs, and distance-hereditary graphs) are defined as graphs that have a hereditarily optimal ordering.[10] Recognizing perfectly orderable graphs is also NP-complete.[11]

Bad orders

[edit]
Main article: Grundy number

The number of colors produced by the greedy coloring for the worst ordering of a given graph is called its Grundy number.[12] Just as finding a good vertex ordering for greedy coloring is difficult, so is finding a bad vertex ordering. It is NP-complete to determine, for a given graph G and number k, whether there exists an ordering of the vertices of G that causes the greedy algorithm to use k or more colors. In particular, this means that it is difficult to find the worst ordering for G.[12]

Graphs for which order is irrelevant

[edit]
Main article: Well-colored graph

The well-colored graphs are the graphs for which all vertex orderings produce the same number of colors. This number of colors, in these graphs, equals both the chromatic number and the Grundy number.[12] They include the cographs, which are exactly the graphs in which all induced subgraphs are well-colored.[13] However, it is co-NP-complete to determine whether a graph is well-colored.[12]

If a random graph is drawn from the Erdős–Rényi model with constant probability of including each edge, then any vertex ordering that is chosen independently of the graph edges leads to a coloring whose number of colors is close to twice the optimal value, with high probability. It remains unknown whether there is any polynomial time method for finding significantly better colorings of these graphs.[3]

Degeneracy

[edit]
The triangular prism and square antiprism, graphs whose greedy colorings using the degeneracy ordering give larger-than-optimal numbers of colors

Because optimal vertex orderings are hard to find, 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, order the subgraph with v removed recursively, and then place v last in the ordering. The largest degree of a removed vertex that this algorithm encounters is called the degeneracy of the graph, denoted d. In the context of greedy coloring, the same ordering strategy is also called the smallest last ordering.[14] This vertex ordering, and the degeneracy, may be computed in linear time.[15] It can be viewed as an improved version of an earlier vertex ordering method, the largest-first ordering, which sorts the vertices in descending order by their degrees.[16]

With the degeneracy ordering, the greedy coloring will use at most d + 1 colors. This is because, when colored, each vertex will have at most d already-colored neighbors, so one of the first d + 1 colors will be free for it to use.[17] Greedy coloring with the degeneracy ordering can find optimal colorings for certain classes of graphs, including trees, pseudoforests, and crown graphs.[18] Markossian, Gasparian & Reed (1996) define a graph to be -perfect if, for and every induced subgraph of , the chromatic number equals the degeneracy plus one. For these graphs, the greedy algorithm with the degeneracy ordering is always optimal.[19] Every -perfect graph must be an even-hole-free graph, because even cycles have chromatic number two and degeneracy two, not matching the equality in the definition of -perfect graphs. If a graph and its complement graph are both even-hole-free, they are both -perfect. The graphs that are both perfect graphs and -perfect graphs are exactly the chordal graphs. On even-hole-free graphs more generally, the degeneracy ordering approximates the optimal coloring to within at most twice the optimal number of colors; that is, its approximation ratio is 2.[20] On unit disk graphs its approximation ratio is 3.[21] The triangular prism is the smallest graph for which one of its degeneracy orderings leads to a non-optimal coloring, and the square antiprism is the smallest graph that cannot be optimally colored using any of its degeneracy orderings.[18]

Adaptive orders

[edit]

Brélaz (1979) proposes a strategy, called DSatur, for vertex ordering in greedy coloring that interleaves the construction of the ordering with the coloring process. In his version of the greedy coloring algorithm, the next vertex to color at each step is chosen as the one with the largest number of distinct colors in its neighborhood. In case of ties, a vertex of maximal degree in the subgraph of uncolored vertices is chosen from the tied vertices. By keeping track of the sets of neighboring colors and their cardinalities at each step, it is possible to implement this method in linear time.[22]

This method can find the optimal colorings for bipartite graphs,[23] all cactus graphs, all wheel graphs, all graphs on at most six vertices, and almost every -colorable graph.[24] Although Lévêque & Maffray (2005) originally claimed that this method finds optimal colorings for the Meyniel graphs, they later found a counterexample to this claim.[25]

Alternative color selection schemes

[edit]

It is possible to define variations of the 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. These include methods in which the uncolored part of the graph is unknown to the algorithm, or in which the algorithm is given some freedom to make better coloring choices than the basic greedy algorithm would.

Online selection

[edit]

Alternative color selection strategies have been studied within the framework of online algorithms. 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, the ratio between the number of colors it uses and the optimal number of colors for the given graph.[26]

If no additional restrictions on the graph are given, the optimal competitive ratio is only slightly sublinear.[27] However, for interval graphs, a constant competitive ratio is possible,[28] while for bipartite graphs 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.[26]

Parsimonous coloring

[edit]

A parsimonious coloring, for a given graph and vertex ordering, has been defined to be a coloring produced by a greedy algorithm that colors the vertices in the given order, and only introduces a new color when all previous colors are adjacent to the given vertex, but can choose which color to use (instead of always choosing the smallest) when it is able to re-use an existing color. The ordered chromatic number is the smallest number of colors that can be obtained for the given ordering in this way, and the ochromatic number is the largest ordered chromatic number among all vertex colorings of a given graph. Despite its different definition, the ochromatic number always equals the Grundy number.[29]

Applications

[edit]

Because it is fast and in many cases can use few colors, greedy coloring can be used in applications where a good but not optimal graph coloring is needed. One of the early applications of the greedy algorithm was to problems such as course scheduling, in which a collection of tasks must be assigned to a given set of time slots, avoiding incompatible tasks being assigned to the same time slot.[4] It can also be used in compilers for register allocation, by applying it to a graph whose vertices represent values to be assigned to registers and whose edges represent conflicts between two values that cannot be assigned to the same register.[30] In many cases, these interference graphs are chordal graphs, allowing greedy coloring to produce an optimal register assignment.[31]

In combinatorial game theory, for an impartial game given in explicit form as a directed acyclic graph whose vertices represent game positions and whose edges represent valid moves from one position to another, the greedy coloring algorithm (using the reverse of a topological ordering of the graph) calculates the nim-value of each position. These values can be used to determine optimal play in any single game or any disjunctive sum of games.[32]

For a graph of maximum degree Δ, any greedy coloring will use at most Δ + 1 colors. Brooks' theorem states that with two exceptions (cliques and odd cycles) at most Δ colors are needed. 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, and each vertex other than the last one has at least one later neighbor. For an ordering with this property, the greedy coloring algorithm uses at most Δ colors.[33]

Notes

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Greedy coloring

View on Grokipedia
from Grokipedia
Greedy coloring is a simple algorithm in for assigning colors to the vertices of an undirected graph such that no two adjacent vertices receive the same color, with each vertex being assigned the smallest possible color number not used by its already neighbors. The algorithm processes the vertices in a fixed order, starting with an arbitrary vertex colored with the first color, and iteratively coloring each subsequent vertex based on the colors forbidden by its previously colored adjacent vertices. This approach always produces a proper coloring, though the number of distinct colors required can vary significantly depending on the chosen ordering of the vertices. A key property of greedy coloring is that it guarantees a proper coloring using at most Δ(G)+1\Delta(G) + 1 colors, where Δ(G)\Delta(G) denotes the maximum degree of the graph GG. This bound is derived from the observation that, when coloring a vertex, at most Δ(G)\Delta(G) colors are forbidden by its neighbors, leaving at least one available color from the set {1,2,…,Δ(G)+1}\{1, 2, \dots, \Delta(G) + 1\}. The bound is tight, as complete graphs KnK_n and odd cycles require exactly nn and 3 colors, respectively, which match Δ+1\Delta + 1 in those cases. However, greedy coloring does not always achieve the chromatic number χ(G)\chi(G), the minimum number of colors needed for any proper coloring, and may use more colors than necessary; for instance, it can require up to Δ(G)+1\Delta(G) + 1 colors on bipartite graphs, which are 2-colorable. The algorithm's simplicity makes it efficient, with a time complexity of O(∣V∣+∣E∣)O(|V| + |E|), where ∣V∣|V| is the number of vertices and ∣E∣|E| is the number of edges, as each edge is examined a constant number of times during neighbor checks. Greedy coloring finds applications in practical problems such as exam scheduling, where courses are vertices and conflicts are edges, as well as in radio frequency assignment and to avoid adjacent regions sharing frequencies or colors. Despite its limitations in optimality, it serves as a foundational technique in and is often used as a starting point for more advanced coloring heuristics.

Overview

Definition

Greedy coloring is a heuristic algorithm for the graph coloring problem, which involves assigning colors to the vertices of an undirected graph such that no two adjacent vertices receive the same color. In this approach, vertices are considered in a predetermined order, and each vertex is assigned the smallest positive integer color that does not conflict with the colors already assigned to its neighboring vertices that appear earlier in the order. A proper coloring of a graph GG is a vertex coloring where adjacent vertices have distinct colors. The chromatic number χ(G)\chi(G) denotes the smallest number of colors needed to achieve a proper coloring of GG. The maximum degree Δ(G)\Delta(G) is the largest number of edges incident to any single vertex in GG. The greedy coloring algorithm guarantees a proper coloring of the graph, but the number of colors it uses may exceed χ(G)\chi(G), making it suboptimal in general. The algorithm operates in linear time with complexity O(∣V∣+∣E∣)O(|V| + |E|), where ∣V∣|V| is the number of vertices and ∣E∣|E| is the number of edges.

Historical Development

The concept of greedy coloring originated in the mid-1960s as researchers sought practical heuristics for approximating the chromatic number of graphs, particularly in applications like timetabling. In 1967, D. J. A. Welsh and M. B. Powell introduced a seminal that orders vertices in decreasing order of degree and assigns the smallest available color to each, establishing an upper bound of Δ(G) + 1 on the number of colors used, where Δ(G) is the maximum degree. This approach marked an early formalization of greedy strategies in graph coloring, building on broader techniques emerging in . Greedy coloring is inherently tied to the general paradigm of greedy algorithms, which prioritize local optimality in decision-making, and it gained traction as a for NP-hard coloring problems in the . Specific advancements in heuristics were contributed by H. A. Kierstead and W. T. Trotter, who in explored online variants of greedy coloring, analyzing algorithms that color vertices as they appear and providing bounds on performance relative to the chromatic number. Their work highlighted the robustness of greedy methods in adversarial settings, influencing subsequent studies on competitive ratios for coloring. The 1980s saw the development of key variants to improve greedy coloring's efficiency, notably the smallest-last ordering introduced by D. W. Matula and L. L. Beck in 1983. This strategy iteratively removes the vertex of smallest degree and colors in reverse order, yielding colorings bounded by the graph's degeneracy plus one, and it was applied to clustering and bandwidth minimization alongside coloring. Such orderings refined the basic greedy framework, emphasizing the role of vertex sequencing in bounding resource usage. Over time, greedy coloring integrated into broader frameworks in , serving as a foundational example in algorithmic design for and proof techniques without major post-2000 innovations altering its core historical trajectory.

Core Algorithm

Step-by-Step Process

The greedy coloring algorithm proceeds by first selecting an arbitrary ordering of the vertices in the graph, denoted as σ=(v1,v2,…,vn)\sigma = (v_1, v_2, \dots, v_n), where nn is the number of vertices. For each vertex viv_i in this sequence, the algorithm assigns the smallest positive integer color that is not used by any of its already-colored neighbors. This neighbor checking involves examining only the adjacent vertices that appear earlier in the ordering σ\sigma, as subsequent vertices have not yet been colored. To illustrate, consider a P4P_4 with vertices v1−v2−v3−v4v_1 - v_2 - v_3 - v_4 and the ordering σ=(v1,v2,v3,v4)\sigma = (v_1, v_2, v_3, v_4). The algorithm begins by assigning color 1 to v1v_1, as it has no colored neighbors. For v2v_2, which is adjacent to v1v_1 (colored 1), the smallest available color is 2. Next, for v3v_3, adjacent to v2v_2 (colored 2), color 1 is available since v3v_3 has no other colored neighbors using it. Finally, for v4v_4, adjacent to v3v_3 (colored 1), color 2 is assigned, as it avoids the color of v3v_3. This results in the coloring: v1:1v_1: 1, v2:2v_2: 2, v3:1v_3: 1, v4:2v_4: 2. The guarantees a proper coloring by , as each vertex viv_i receives a color distinct from all its previously colored neighbors, ensuring no adjacent vertices share the same color at the time of assignment; any adjacency to later vertices is handled when those vertices are colored. The specific outcome, such as the number of colors used, can vary depending on the chosen ordering σ\sigma.

Pseudocode and Simple Example

The greedy coloring algorithm can be expressed in pseudocode as follows, where the input graph GG has nn vertices ordered as v1,v2,…,vnv_1, v_2, \dots, v_n, and the output is a color assignment array c[1..n]c[1..n] using positive integers starting from 1.

function GreedyColor(G, order): initialize color array c[1..n] = 0 // 0 indicates uncolored for i = 1 to n: v = order[i] used = empty set for each neighbor u of v: if c[u] != 0: add c[u] to used c[v] = 1 while c[v] in used: c[v] = c[v] + 1 return c

function GreedyColor(G, order): initialize color array c[1..n] = 0 // 0 indicates uncolored for i = 1 to n: v = order[i] used = empty set for each neighbor u of v: if c[u] != 0: add c[u] to used c[v] = 1 while c[v] in used: c[v] = c[v] + 1 return c

In this pseudocode, for each vertex vv, the set used collects the colors of its already colored neighbors. The color cc is then set to the smallest positive integer not in used, found by starting at 1 and incrementing until an unused color is found. To illustrate, consider the C5C_5 with vertices labeled v1,v2,v3,v4,v5v_1, v_2, v_3, v_4, v_5 and edges v1−v2v_1-v_2, v2−v3v_2-v_3, v3−v4v_3-v_4, v4−v5v_4-v_5, v5−v1v_5-v_1. The chromatic number χ(C5)=3\chi(C_5) = 3, as it is an odd cycle requiring three colors for a proper coloring. Applying the algorithm in the order v1,v2,v3,v4,v5v_1, v_2, v_3, v_4, v_5:
  • Color v1v_1: no colored neighbors, so used = ∅\emptyset, assign 1.
  • Color v2v_2: neighbor v1v_1 colored 1, used = {1}, assign 2.
  • Color v3v_3: neighbor v2v_2 colored 2, used = {2}, assign 1.
  • Color v4v_4: neighbor v3v_3 colored 1, used = {1}, assign 2.
  • Color v5v_5: neighbors v4v_4 colored 2 and v1v_1 colored 1, used = {1,2}, assign 3.
This results in the coloring: v1:1v_1: 1, v2:2v_2: 2, v3:1v_3: 1, v4:2v_4: 2, v5:3v_5: 3, using 3 colors. In this case, the greedy algorithm achieves the optimal coloring for this ordering, though different orderings may also yield 3 colors given the graph's structure.

Vertex Ordering Strategies

Importance of Ordering

The choice of vertex ordering profoundly affects the performance of the greedy coloring algorithm, as it determines the sequence in which vertices are assigned colors based on their already-colored neighbors. For a fixed graph GG, different orderings can yield proper colorings using a number of colors close to the chromatic number χ(G)\chi(G) in favorable cases or far exceeding χ(G)\chi(G) in unfavorable ones, highlighting the algorithm's sensitivity to this parameter. This dependence arises because each vertex receives the smallest available color not forbidden by its earlier neighbors, so the timing of a vertex's processing relative to its adjacent vertices directly influences color reuse. A striking illustration of this order sensitivity occurs in bipartite graphs, which have χ(G)=2\chi(G) = 2. The crown graph, defined as the Kn,nK_{n,n} minus a and consisting of 2n2n vertices, can be colored with 2 colors in an appropriate order but requires up to nn colors under a poor ordering in the . In this adversarial ordering, vertices are processed in a way that maximizes the distinct colors needed for non-adjacent vertices that become "blocked" from low-numbered colors due to their neighbors' assignments. Such examples demonstrate how ordering can amplify the number of colors beyond the graph's inherent coloring requirements. The impact of ordering is further modulated by the graph's degree sequence and structural properties, including the sizes of cliques and independent sets. Graphs with large exhibit less variability, as the clique size provides a lower bound on both χ(G)\chi(G) and the colors used in any , limiting the room for ordering-induced inefficiency. Conversely, in graphs dominated by independent sets or sparse connections, like trees or bipartite graphs without dense substructures, a suboptimal order can force unnecessary new colors by delaying the coloring of high-degree vertices until many low colors are partially occupied. These factors emphasize that while the is efficient, its color efficiency hinges on order choices that align with the graph's . To quantify this worst-case behavior across all orderings, the greedy chromatic number, also known as the Grundy number Γ(G)\Gamma(G), is defined as the maximum number of colors used by the over every possible vertex ordering of GG. This measure reflects the algorithm's potential for poor performance and serves as a theoretical benchmark for understanding ordering effects, though computing Γ(G)\Gamma(G) is generally intractable.

Favorable Ordering Methods

One prominent favorable ordering strategy for greedy coloring is the largest-first ordering, also known as the Welsh-Powell ordering, which arranges the vertices in decreasing order of their degrees. In this approach, vertices with the highest degrees are colored first, which tends to assign colors to highly constrained vertices early, potentially reducing the total number of colors needed compared to arbitrary orders. This method guarantees that the greedy algorithm uses at most Δ+1\Delta + 1 colors, where Δ\Delta is the maximum degree of the graph, matching the general upper bound for greedy coloring but often achieving tighter results in practice. Another effective strategy is the smallest-last ordering, proposed by Matula and Beck, which constructs the vertex order by repeatedly selecting and removing a vertex of minimum degree from the remaining graph until none are left, then reversing the removal sequence to determine the coloring order. This ordering prioritizes vertices with fewer constraints later in the process, allowing the to reuse colors more efficiently for low-degree vertices. Like the largest-first approach, it ensures the use of at most Δ+1\Delta + 1 colors, but it is particularly advantageous for graphs with varying degree distributions by leveraging the graph's degeneracy. On complete bipartite graphs Km,nK_{m,n}, both largest-first and smallest-last orderings yield the optimal 2-coloring when applied to the greedy algorithm. For instance, in largest-first ordering on Km,nK_{m,n} with m≤nm \leq n, the higher-degree vertices in the smaller partition are colored first, all receiving the same color since their neighbors are uncolored, followed by the lower-degree vertices in the larger partition, which receive a second color. A similar process occurs with smallest-last, where low-degree vertices are deferred, enabling efficient 2-coloring. Empirically, these orderings often produce colorings that use at most Δ+1\Delta + 1 colors while performing close to the chromatic number on many graph classes, such as sparse or planar graphs, outperforming random orderings in terms of color efficiency.

Unfavorable Ordering Methods

Unfavorable ordering methods in greedy coloring refer to vertex orderings that result in a significantly higher number of colors than the chromatic number χ(G)\chi(G) of the graph, often approaching the worst-case bound of Δ(G)+1\Delta(G) + 1 or even the number of vertices in pathological cases. These orderings contrast with favorable strategies by prioritizing vertices in a way that leaves densely connected subgraphs for later processing, forcing the algorithm to assign new colors repeatedly due to conflicts with previously colored neighbors. The maximum number of colors induced by any ordering is known as the Grundy number Γ(G)\Gamma(G), which can exceed χ(G)\chi(G) substantially. One such unfavorable method is the reverse largest-first ordering, also called smallest-degree-first, where vertices are sorted in ascending order of their degrees and colored from lowest to highest degree. This approach colors low-degree vertices early, often allowing them to share colors freely, but delays high-degree vertices, which then face restrictions from a diverse set of already-used colors in their neighborhoods, leading to excessive color usage. For instance, in graphs with uneven degree distributions, this ordering can perform poorly by not resolving high-conflict areas promptly. A classic example illustrating the impact of unfavorable orderings is the crown graph, a Hn,nH_{n,n} formed by the complete bipartite graph Kn,nK_{n,n} minus a , which has χ(Hn,n)=2\chi(H_{n,n}) = 2. However, if vertices are ordered by alternating one vertex from each matched pair (e.g., u1,v1,u2,v2,…,un,vnu_1, v_1, u_2, v_2, \dots, u_n, v_n), the assigns a distinct new color to each subsequent vertex due to adjacency constraints, resulting in nn colors—far exceeding the optimal. This demonstrates how specific orderings can amplify the algorithm's inefficiency even in simple bipartite structures. Pathological cases often involve orderings that color large independent sets early, assigning them the same minimal color, while deferring s or dense subgraphs to the end. In such scenarios, the independent set uses just one color, but the subsequent vertices, each adjacent to many previously colored neighbors (potentially spanning multiple colors if the independent set connects broadly), require distinct new colors, pushing the total far beyond χ(G)\chi(G). Mycielski graphs, constructed to have high chromatic numbers without triangles, exhibit similar behavior under bad orderings, where greedy coloring can use χ(G)+1\chi(G) + 1 or more colors by sequencing vertices to maximize neighborhood color diversity at each step. Finding an ordering that maximizes the number of colors in greedy coloring—equivalent to computing the Grundy number Γ(G)\Gamma(G)—is NP-hard, even for restricted graph classes like bipartite graphs. This computational difficulty underscores the challenge of deliberately constructing unfavorable orderings, limiting their practical use to theoretical analysis rather than algorithmic design.

Graphs Insensitive to Ordering

In graph theory, certain classes of graphs exhibit the property that the greedy coloring algorithm produces a coloring using exactly the chromatic number χ(G)\chi(G) of colors, irrespective of the vertex ordering chosen. This insensitivity to ordering occurs precisely when χ(G)=Δ(G)+1\chi(G) = \Delta(G) + 1, where Δ(G)\Delta(G) is the maximum degree of the graph. By Brooks' theorem, the only connected graphs satisfying this condition are complete graphs and odd cycles. For complete graphs KnK_n, the chromatic number is χ(Kn)=n\chi(K_n) = n, and Δ(Kn)=n−1\Delta(K_n) = n-1. The , in any vertex ordering, assigns a new color to each successive vertex because every previously colored vertex is adjacent to it, resulting in exactly nn colors used. This holds since the algorithm always produces a proper coloring requiring at least χ(G)\chi(G) colors and at most Δ(G)+1=n\Delta(G) + 1 = n colors. Odd cycles C2k+1C_{2k+1} (for k≥1k \geq 1) have χ(C2k+1)=3\chi(C_{2k+1}) = 3 and Δ(C2k+1)=2\Delta(C_{2k+1}) = 2. The uses at most Δ+1=3\Delta + 1 = 3 colors in any ordering. However, since no proper 2-coloring exists due to the odd length, every requires exactly 3 colors. For example, in C5C_5, various orderings consistently demand a third color for at least one vertex to avoid conflicts with its two neighbors. These classes contrast with most graphs, where the number of colors used by greedy coloring varies significantly with the ordering, often exceeding χ(G)\chi(G).

Degeneracy-Based Ordering

A graph GG is defined as kk-degenerate if every nonempty induced subgraph of GG contains a vertex of degree at most kk. The degeneracy of a graph GG, denoted d(G)d(G), is the smallest integer kk such that GG is kk-degenerate. A degeneracy ordering of a kk-degenerate graph can be constructed algorithmically by repeatedly selecting and removing a vertex of degree at most kk from the induced subgraph on the remaining vertices until no vertices are left; this elimination sequence, when reversed, yields an ordering σ=(v1,v2,…,vn)\sigma = (v_1, v_2, \dots, v_n) in which each vertex viv_i has at most kk neighbors that appear after it in σ\sigma (i.e., among vi+1,…,vnv_{i+1}, \dots, v_n). Applying the greedy coloring algorithm in this degeneracy ordering—processing vertices from vnv_n to v1v_1 and assigning to each the smallest color not used by its already colored neighbors—requires at most d(G)+1d(G) + 1 colors. To see this, consider any vertex viv_i during coloring: its already colored neighbors are precisely those that appear after it in σ\sigma, of which there are at most d(G)d(G); thus, at most d(G)d(G) colors are forbidden, leaving at least one available from the set {1,2,…,d(G)+1}\{1, 2, \dots, d(G) + 1\}. For example, every simple planar graph is 5-degenerate, as follows from Euler's formula implying that the average degree is less than 6 and thus every induced subgraph has minimum degree at most 5; therefore, greedy coloring in a degeneracy ordering uses at most 6 colors on planar graphs.

Adaptive Ordering Techniques

Adaptive ordering techniques dynamically determine the sequence in which vertices are colored during the greedy process, adjusting based on the current partial coloring to prioritize more constrained vertices and potentially yield fewer colors than fixed-order approaches. Unlike static strategies such as largest-first ordering, which predefine the sequence regardless of progress, adaptive methods select the next vertex at each step according to heuristics that reflect the evolving state of the graph, such as the impact of recently assigned colors. This responsiveness can improve solution quality on dense or irregular graphs, though it increases runtime compared to linear-time fixed-order greedy coloring. A foundational adaptive technique is the DSATUR (Degree of SATURation) algorithm, developed by Brélaz in 1979. DSATUR proceeds by repeatedly selecting the uncolored vertex with the maximum saturation degree—the count of distinct colors among its already colored neighbors—and assigning it the smallest available color not used by those neighbors. In case of ties, the vertex with the highest degree (considering both colored and uncolored neighbors) is chosen. This dynamic prioritization focuses on vertices facing the most immediate constraints, often producing colorings closer to the chromatic number than simple greedy methods, especially for random graphs. For example, on the DIMACS benchmark suite, DSATUR frequently achieves optimal or near-optimal results with fewer colors than static degree-based orders. More broadly, dynamic greedy variants extend this idea by reordering or selecting uncolored vertices based on partial coloring metrics, such as prioritizing those with the highest remaining degree among uncolored neighbors to anticipate future conflicts. These approaches maintain the core greedy color selection but adapt the order on-the-fly, leading to better average-case performance on sparse graphs while remaining polynomial-time. However, naive implementations incur O(n^2) time due to repeated scans for the maximum-priority vertex, though optimized versions using priority queues or bucketing reduce this to O(n + m log n), still higher than the O(n + m) of standard greedy. Iterative adaptive methods further refine colorings by performing multiple passes over the graph, using feedback from prior iterations to adjust orders. Culberson's Iterated (1992) initializes a coloring via standard greedy, then iteratively perturbs the vertex order—such as by reversing segments or applying look-ahead to high-conflict regions—and recolors until no reduction in color count occurs or a limit is reached. This repetition explores the coloring landscape more thoroughly, escaping poor local minima and often finding optimal k-colorings for graphs where single-pass greedy fails, as demonstrated on k-colorable random graphs. In applications like for compilers, adaptive ordering tailors the greedy process to live range analysis, prioritizing variables with longer or more overlapping live ranges to minimize spills. For instance, the greedy allocator (Olesen, 2011) dynamically splits and reorders live ranges based on their size and interference patterns during coloring, reducing code size by 1-2% and improving speed by up to 10% over prior methods on benchmark programs. This adaptation ensures critical variables receive registers early, enhancing overall efficiency in resource-constrained environments.

Color Selection Variations

Standard Smallest-Color Rule

In the standard smallest-color rule applied to greedy graph coloring, a vertex is assigned the smallest positive integer color that differs from all colors already used by its previously neighbors in the given vertex ordering. This selection mechanism guarantees a proper coloring, as adjacent vertices receive distinct colors by construction. To implement this rule efficiently, for each vertex, the colors of its colored neighbors are collected into a set or, for better performance with bounded color ranges, a bit array to identify forbidden colors; the smallest index not marked as used is then selected. The colors assigned range from 1 to some kk, where k≤Δ+1k \leq \Delta + 1 and Δ\Delta is the maximum degree of the graph, since each vertex has at most Δ\Delta colored neighbors at the time of assignment, leaving at least one available color in the set {1,2,…,Δ+1}\{1, 2, \dots, \Delta + 1\}. This rule contrasts with the largest-color variant, which assigns the highest available color instead, though the smallest-color approach is the conventional default and tends to produce more compact color sets in practice.

Online Coloring Selection

In online graph coloring, vertices are presented to the algorithm one by one in an adversarial order, and each vertex must be assigned a color irrevocably upon arrival, without knowledge of future vertices or edges. The algorithm bases its decision solely on the subgraph induced by the vertices seen so far, ensuring that the color chosen does not conflict with any previously colored adjacent vertices. The greedy variant for coloring, known as First-Fit, assigns to each arriving vertex the smallest positive integer color that is not used by any of its already colored neighbors. This approach mirrors the standard smallest-color rule but operates sequentially as vertices arrive, potentially leading to suboptimal color usage due to the lack of global information. A notable performance measure for online algorithms is the competitive ratio, defined as the worst-case ratio of colors used by the algorithm to the chromatic number of the graph. For First-Fit on , which are 2-colorable, the algorithm uses at most ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 colors for any with nn vertices, achieving a competitive ratio of Θ(log⁡n)\Theta(\log n), which is optimal among deterministic online algorithms. An illustrative example of poor performance relative to the offline optimum is the complete TkT_k of height kk, which has 2k−12^k - 1 vertices and is 2-colorable. When presented in a specific adversarial order—such as level-by-level from the leaves upward—First-Fit is forced to use kk distinct colors, as each level introduces vertices adjacent only to higher levels already using new colors. This construction demonstrates that the competitive ratio lower bound of Ω(log⁡n)\Omega(\log n) is tight for trees.

Parsimonious Coloring Method

The parsimonious coloring method refers to the application of the standard smallest-color algorithm to a fixed vertex ordering, where each vertex is assigned the smallest positive integer color not used by its previously colored neighbors. This produces a proper coloring that reuses existing colors whenever possible, introducing a new color only when all previously used colors are forbidden by neighbors. The method was introduced in the study of ordered colorings, with the ochromatic number χ′(G)\chi'(G) defined as the maximum number of colors used in a parsimonious coloring over all possible vertex orderings. A key result is that the ochromatic number equals the Grundy number of the graph. On specific graph classes like interval graphs, an appropriate ordering—such as by left endpoint—allows parsimonious coloring to achieve the optimal chromatic number, equal to the size of the maximum . In general graphs, the number of colors depends on the ordering, and the ochromatic number measures the worst-case performance. This method shares similarities with online coloring selection, as both involve sequential irrevocable decisions, but parsimonious coloring uses a known fixed ordering rather than an adversarial presentation.

Performance Guarantees

Upper Bounds on Colors

The greedy coloring algorithm, applied to any vertex ordering of a graph GG, uses at most Δ(G)+1\Delta(G) + 1 colors, where Δ(G)\Delta(G) denotes the maximum degree of GG. This bound arises because, when assigning a color to any vertex vv, at most Δ(G)\Delta(G) neighbors of vv can have been colored previously, leaving at least one color available from the set {1,2,…,Δ(G)+1}\{1, 2, \dots, \Delta(G) + 1\} via the minimum excluded value (mex) rule. Thus, the chromatic number satisfies χ(G)≤Δ(G)+1\chi(G) \leq \Delta(G) + 1. The Welsh-Powell algorithm, a specific greedy coloring variant that orders vertices in nonincreasing order of their degrees, also adheres to this Δ(G)+1\Delta(G) + 1 upper bound. In this ordering, when a vertex vv of degree d(v)d(v) is colored, at most d(v)d(v) higher-degree vertices precede it, but since d(v)≤Δ(G)d(v) \leq \Delta(G), the mex remains at most Δ(G)+1\Delta(G) + 1. This approach was originally proposed for timetabling applications, providing a practical while guaranteeing the same worst-case performance as general greedy coloring. A tighter bound is achievable using the degeneracy d(G)d(G) of GG, defined as the smallest dd such that every of GG has a vertex of degree at most dd. With a degeneracy ordering—where vertices are repeatedly removed in an order ensuring each has at most dd neighbors later in the sequence—greedy coloring uses at most d(G)+1d(G) + 1 colors. Here, upon coloring any vertex vv, at most d(G)d(G) previous neighbors exist, so the mex is at most d(G)+1d(G) + 1, yielding χg(G)≤d(G)+1\chi_g(G) \leq d(G) + 1, where χg(G)\chi_g(G) is the number of colors used. Since d(G)≤Δ(G)d(G) \leq \Delta(G), this refines the fundamental bound. In general, for any vertex ordering σ=(v1,v2,…,vn)\sigma = (v_1, v_2, \dots, v_n), the number of colors used by greedy coloring is at most 1+max⁡vdeg⁡σ(v)1 + \max_v \deg_\sigma(v), where deg⁡σ(v)\deg_\sigma(v) is the number of neighbors of vv that appear before vv in σ\sigma. This follows directly from the mex assignment: the color of vv is 1+1 + the number of distinct colors among its previous neighbors, which is at most 1+deg⁡σ(v)1 + \deg_\sigma(v). The maximum over all vv thus bounds the total colors, simplifying to Δ(G)+1\Delta(G) + 1 when deg⁡σ(v)≤Δ(G)\deg_\sigma(v) \leq \Delta(G) for all vv.

Worst-Case Scenarios

In the worst-case scenarios for greedy coloring, certain graphs and vertex orderings cause the algorithm to use significantly more colors than the chromatic number χ(G), highlighting its sensitivity to ordering. A classic example occurs in bipartite graphs, which have χ(G) = 2. With an unfavorable vertex ordering, the greedy algorithm can be forced to use Ω(log n) colors on trees, a subclass of bipartite graphs with n vertices, as each new vertex in the ordering can be adjacent to vertices of all previously used colors, blocking reuse until a new color is needed. This demonstrates how even simple structures can lead to logarithmic overuse relative to the optimal. A more dramatic illustration is the crown graph, a formed by two disjoint sets of k vertices each, with edges connecting vertices from different sets except for matching pairs (i to i). This graph has χ(G) = 2 and maximum degree Δ = k-1. However, with the ordering that alternates vertices from the two sets (v_1, u_1, v_2, u_2, ..., v_k, u_k), the assigns a new color to each u_i because it is adjacent to all previously colored v_j (j ≤ i) that have distinct colors, resulting in k colors used overall. For large k (n = 2k vertices), this equates to Θ(n) colors versus the optimal 2, showing extreme degradation. For a small instance with k=2 (n=4, the cycle C_4), a bad ordering can use 3 colors instead of 2, but the general construction scales poorly. These examples stem from early analyses of greedy performance.

Approximation Ratios

Greedy coloring functions as an for the chromatic number problem, which seeks the minimum number of colors needed to properly color a graph GG. In its basic form, the algorithm processes vertices in a fixed order and assigns to each the smallest color not used by its earlier neighbors, guaranteeing a proper coloring with at most Δ(G)+1\Delta(G) + 1 colors, where Δ(G)\Delta(G) is the maximum degree of GG. By Brooks' theorem, for any connected graph that is neither a nor an odd cycle, χ(G)≤Δ(G)\chi(G) \leq \Delta(G), so the achieves an approximation ratio of at most Δ(G)+1\Delta(G) + 1 relative to the optimal χ(G)\chi(G). In the exceptional cases of cliques or odd cycles, χ(G)=Δ(G)+1\chi(G) = \Delta(G) + 1, and a suitable vertex ordering allows the to match this exactly, though adversarial orderings may perform worse. To enhance the approximation quality, the can employ a degeneracy-based ordering. A graph GG is dd-degenerate if every has minimum degree at most dd, and such graphs admit a vertex elimination ordering where each vertex has at most dd neighbors earlier in the order. Applying greedy coloring to the reverse of this ordering (i.e., processing low-degree vertices last) uses at most d+1d + 1 colors. Since χ(G)≤d+1\chi(G) \leq d + 1 for dd-degenerate graphs and d≤Δ(G)d \leq \Delta(G), this yields an O(d+1)O(d + 1)- for χ(G)\chi(G), which is at most Δ(G)+1\Delta(G) + 1. This approach is particularly effective for sparse graphs, where dd is often much smaller than Δ(G)\Delta(G). The chromatic number problem is NP-hard to approximate within any constant factor unless P = NP, as established by inapproximability results showing it is NP-hard to approximate χ(G)\chi(G) within a factor of n1−ϵn^{1-\epsilon} for any ϵ>0\epsilon > 0, unless NP = ZPP. Consequently, while greedy coloring does not provide a constant-factor guarantee in general, it remains a widely used practical heuristic due to its simplicity, efficiency, and strong worst-case bounds tied to graph parameters like degree and degeneracy. In the 2020s, variants of greedy coloring have been integrated into parallel frameworks for large-scale graphs, offering approximation guarantees alongside low work and depth complexities suitable for distributed computing environments.

Applications

Scheduling and Optimization

Greedy coloring finds significant application in scheduling problems modeled by interval graphs, where tasks or jobs are represented as intervals on a timeline, and resources must be allocated such that no two overlapping intervals share the same resource. In this context, sorting the intervals by their left endpoints and applying the greedy coloring algorithm—assigning to each interval the smallest color not used by its already-colored neighboring intervals—yields an optimal coloring that uses exactly the maximum number of intervals overlapping at any point, which equals the clique number of the graph and thus the chromatic number. This approach is optimal because interval graphs are perfect graphs, ensuring that the greedy method in this specific ordering matches the minimum number of resources required for conflict-free allocation. In optimization problems involving computations, the choice of vertex ordering for greedy coloring is closely related to bandwidth minimization, where the goal is to arrange vertices in a linear order that minimizes the maximum difference in positions of adjacent vertices, thereby reducing the bandwidth of the . A low-bandwidth ordering facilitates efficient storage and faster numerical algorithms, such as , by limiting fill-in and non-zero elements within a narrow band around the diagonal. Greedy coloring heuristics often employ orderings that approximate such bandwidth-minimizing layouts, particularly for chordal graphs arising from banded matrices, where the chromatic number is bounded by the bandwidth plus one, enabling practical approximations with at most Δ+1 colors. Register allocation in optimization can be approximated using greedy coloring on the interference graph, where vertices represent live ranges of variables and edges indicate simultaneous liveness, preventing assignment to the same register. The , applied to this graph, assigns registers (colors) such that adjacent vertices receive different ones, and since the interference graph typically has maximum degree Δ less than the number of available registers, Δ+1 colors suffice to allocate registers without spilling in most cases, providing a bounded to the optimal assignment. This method leverages the performance guarantee that greedy coloring uses at most Δ+1 colors, ensuring efficient resource use in theoretical models of computation. Greedy coloring also connects to bin packing in , where colors represent bins and vertices are unit-size items that must be packed into bins without violating capacity constraints defined by the of color classes—no two adjacent vertices in the same bin. The greedy assignment to the smallest available color mirrors first-fit strategies in bin packing, partitioning the graph into independent sets (bins) with a bounded number of bins relative to the optimal, particularly when the ordering prioritizes higher-degree vertices to minimize overuse of bins. This analogy highlights how greedy coloring provides an for with conflict constraints, using at most Δ+1 bins in the worst case.

Compiler and Resource Allocation

In compiler design, greedy plays a central role in , particularly through the Chaitin-Briggs method, which models live ranges of variables as nodes in an interference graph and edges representing overlapping lifetimes. The greedy assigns the smallest available color (register) to each node in an order that prioritizes high-degree nodes to minimize spills, where uncolorable nodes trigger insertions of load and store instructions to temporary locations. This approach approximates optimal allocation within the fixed number of hardware registers, reducing execution overhead from accesses while maintaining program semantics. In , greedy coloring addresses channel assignment to mitigate interference by constructing an interference graph where nodes represent transmitters or links and edges denote potential co-channel conflicts based on signal overlap. The algorithm iteratively assigns the lowest-numbered channel (color) to each node that avoids reuse by adjacent nodes, enabling efficient spectrum utilization in dense deployments like networks. This method balances computational simplicity with practical performance, often achieving near-optimal interference reduction in dynamic environments without exhaustive search. For VLSI design, greedy coloring facilitates channel routing by modeling nets as intervals on a linear track, forming an where the left-to-right endpoint ordering ensures optimal track assignment equivalent to the maximum size, determining the minimum channel . This technique routes horizontal wires in a single-layer channel by coloring intervals to avoid overlaps, supporting scalable layout automation in integrated circuits. Post-2010 developments in GPU scheduling leverage on task dependency graphs to partition workloads into independent sets for concurrent execution, enhancing parallelism in irregular computations like graph analytics. By coloring tasks to identify conflict-free groups, the method dynamically schedules threads across streaming multiprocessors, improving resource utilization and reducing synchronization overhead in frameworks like .

References

  1. https://www.whitman.edu/mathematics/cgt_online/book/section05.08.html
  2. https://web.math.princeton.edu/math_alive/5/Notes2.pdf
  3. https://www.cs.cornell.edu/courses/JavaAndDS/files/graphColoring.pdf
  4. https://arxiv.org/pdf/1505.05825
  5. https://www.semanticscholar.org/paper/An-upper-bound-for-the-chromatic-number-of-a-graph-Welsh-Powell/dc7a42a09ca239778ed985cebccf5db6356914c3
  6. https://www.cs.toronto.edu/~bor/2421f19/papers/kierstead-survey.pdf
  7. https://dl.acm.org/doi/10.1145/2402.322385
  8. https://www.semanticscholar.org/paper/Smallest-last-ordering-and-clustering-and-graph-Matula-Beck/7c1a0f7054d496e71cc697202b84d8a5c652328a
  9. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture24.pdf
  10. https://www.classes.cs.uchicago.edu/archive/2006/winter/37000-1/01.pdf
  11. https://people.math.sc.edu/lu/teaching/2005fall_776/lecture10.pdf
  12. https://thorehusfeldt.com/wp-content/uploads/2010/08/gca.pdf
  13. https://www.researchtrend.net/ijet/pdf/Greedy%2520Graph%2520Coloring%2520Algorithm%2520based%2520on%2520Depth%2520First%2520Search%2520Sumit%2520Gupta%25202235j4.pdf
  14. https://www.mathsjournal.com/pdf/2022/vol7issue2/PartB/7-2-5-115.pdf
  15. https://www.cs.purdue.edu/homes/apothen/Papers/acyclic-SISC.pdf
  16. https://arxiv.org/pdf/1507.01080
  17. https://academic.oup.com/comjnl/article-abstract/10/1/85/376064
  18. https://dl.acm.org/doi/pdf/10.1145/2402.322385
  19. https://www.sciencedirect.com/science/article/pii/0196677491900406
  20. https://inria.hal.science/hal-00905927/document
  21. https://www.math.brown.edu/~res/M123/brooks.pdf
  22. https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/kdegenerate-graphs/45829E7755FA1F4D72FD84530F492E8A
  23. https://www.sciencedirect.com/science/article/pii/S002198006880081X
  24. https://dl.acm.org/doi/10.1145/359094.359101
  25. https://arxiv.org/pdf/2108.09329
  26. https://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
  27. https://cse.buffalo.edu/~hungngo/classes/2004/594/notes/Coloring-intro.pdf
  28. https://cstheory.stackexchange.com/questions/52736/how-do-you-achieve-linear-time-complexity-of-greedy-graph-coloring
  29. https://dl.acm.org/doi/fullHtml/10.1145/3605573.3605623
  30. https://salil.seas.harvard.edu/sites/g/files/omnuum4266/files/salil/files/cs120-fall2021-ps7.pdf
  31. https://users.renyi.hu/~gyarfas/Cikkek/33_GyarfasLehel_OnLineAndFirstFitColoringsOfGraphs.pdf
  32. https://users.renyi.hu/~p_erdos/1987-18.pdf
  33. https://www.sciencedirect.com/science/article/pii/002001909190245D
  34. https://arxiv.org/pdf/2103.11917.pdf
  35. https://www.mimuw.edu.pl/~aszek/chromatic/lec3.pdf
  36. https://digitalcommons.georgiasouthern.edu/cgi/viewcontent.cgi?article=1409&context=tag
  37. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v30i4p18/pdf
  38. https://hal.science/hal-02167055v1
  39. https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf
  40. https://arxiv.org/abs/2309.12670
  41. https://arxiv.org/abs/2008.11321
  42. https://ics.uci.edu/~eppstein/163/lecture6c.pdf
  43. https://www.cs.purdue.edu/homes/apothen/Papers/hessian-coloring-joc.pdf
  44. https://www.cs.utexas.edu/~pingali/CS380C/2007fa/papers/p66-chaitin.pdf
  45. https://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1378.pdf
  46. https://www.cs.utexas.edu/~mckinley/380C/lecs/briggs-thesis-1992.pdf
  47. https://dl.acm.org/doi/10.1145/1094549.1094554
  48. https://www.mdpi.com/2073-8994/10/3/65
  49. https://ieeexplore.ieee.org/document/68407
  50. https://arxiv.org/pdf/2112.00132
Add your contribution
Related Hubs
User Avatar
No comments yet.