#9575: Grundy coloring of a graph
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.5.2
Component: graph theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
This patch adds the function ``grundy_coloring``, which computes the worst
case of a first-fit coloring algorithm. Here are some explanations from
the function's help :
A first-fit coloring is obtained by sequentially coloring the
vertices of a graph, assigning them the smallest color not already
assigned to one of its neighbors. The result is clearly a proper
coloring, which usually requires much more colors than an optimal
vertex coloring of the graph, and heavily depends on the ordering
of the vertices.
The number of colors required by the worst-case application of
this algorithm on a graph `G` is called the Grundy number, written
`\Gamma (G)`.
Equivalent formulation :
Equivalently, a Grundy coloring is a proper vertex coloring such
that any vertex colored with `i` has, for every `j<i`, a neighbor
colored with `j`. This can define a Linear Program, which is used
here to compute the Grundy number of a graph.
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9575>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
