id	summary	reporter	owner	description	type	status	priority	milestone	component	resolution	keywords	cc	work_issues	upstream	reviewer	author	merged	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<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

"	enhancement	closed	major	sage-4.5.3	graph theory	fixed				N/A	Leonardo Sampaio	Nathann Cohen	sage-4.5.3.alpha0