Lesson 6

One of the most popular heuristics for graph coloring is the greedy one: we will iterate over the vertices of the graph in some order and color the current vertex with the minimal allowed color. In this way, the graph will be quickly and correctly colored, but not necessarily in a small number of colors. The resulting number of colors depends on both the graph itself and the chosen permutation of vertices. Nevertheless, even this simplest algorithm shows that a graph with small degree can definitely be colored with a small number of colors: \[\chi(G) \le \Delta(G) + 1 \ .\] Indeed, since a vertex has at most \(\Delta(G)\) neighbors, among \(\Delta(G)+1\) colors there is definitely at least one allowed.

It is easy to see that there exist vertex permutations for which this simple greedy algorithm produces an optimal coloring. For example, we can take the optimal coloring and consider such a permutation: first go the vertices of one color, then of some other, then another, and so on. For example, the code below succeeds in coloring the Petersen graph optimally in three colors using this greedy heuristic.

import networkx as nx

g = nx.petersen_graph()
print(nx.coloring.greedy_color(g, strategy='largest_first'))

{0: 0, 1: 1, 2: 0, 3: 1, 4: 2, 5: 1, 6: 0, 7: 2, 8: 2, 9: 1}