GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/GreedyColor

GraphTheory

 GreedyColor

 Calling Sequence GreedyColor(G, perm)

Parameters

 G - undirected unweighted graph perm - (optional) list of vertex labels

Description

 • 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 a list that specifies the coloring of the vertices.

Examples

 > with(GraphTheory):
 > C6 := CycleGraph(6);
 ${\mathrm{C6}}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 6 vertices and 6 edge\left(s\right)}}$ (1)
 > GreedyColor(C6);
 ${2}{,}\left[{0}{,}{1}{,}{0}{,}{1}{,}{0}{,}{1}\right]$ (2)
 > GreedyColor(C6, [1, 4, 2, 5, 3, 6]);
 ${3}{,}\left[{0}{,}{1}{,}{2}{,}{0}{,}{1}{,}{2}\right]$ (3)