GraphTheory
GreedyColor
Calling Sequence
Parameters
Description
Examples
GreedyColor(G, perm)
G

undirected unweighted graph
perm
(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 a list that specifies the coloring of the vertices.
$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$
$\mathrm{C6}\u2254\mathrm{CycleGraph}\left(6\right)$
${\mathrm{C6}}{\u2254}{\mathrm{Graph\; 1:\; an\; undirected\; unweighted\; graph\; with\; 6\; vertices\; and\; 6\; edge(s)}}$
$\mathrm{GreedyColor}\left(\mathrm{C6}\right)$
${2}{,}\left[{0}{\,}{1}{\,}{0}{\,}{1}{\,}{0}{\,}{1}\right]$
$\mathrm{GreedyColor}\left(\mathrm{C6}\,\left[1\,4\,2\,5\,3\,6\right]\right)$
${3}{,}\left[{0}{\,}{1}{\,}{2}{\,}{0}{\,}{1}{\,}{2}\right]$
See Also
ChromaticNumber
GreedyClique
IsVertexColorable
Download Help Document
What kind of issue would you like to report? (Optional)