color graph with greedy algorithm
undirected unweighted graph
(optional) list of vertex labels
The GreedyColor command colors the vertices of the graph in the order given by perm, one at a time, assigning to each vertex the smallest available color. If the permutation perm is not specified, a heuristic is used, the permutation being given by the following rule: a vertex with lowest degree is removed from the graph, the heuristic permutation for the remaining graph is determined recursively, and the removed vertex is put at the end of this permutation. This yields a coloring with at most d+1 colors, where d is such that every subgraph of G contains a vertex of degree at most d. The parameter d is also known as the degeneracy of G.
The output consists the number of colors used, followed by a list that specifies the coloring of the vertices.
C6 ≔ CycleGraph⁡6
C6≔Graph 1: an undirected graph with 6 vertices and 6 edge(s)
Download Help Document