id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
9575,Grundy coloring of a graph,ncohen,jason ncohen rlm,"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