Grundy coloring of a graph

[ncohen]

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

[lsampaio]

It works, the documentation is ok. I believe it can be accepted.

[ncohen]

Yeahhhhhhhhhhhhhhhhhhhh !!!!!!

Thank youuuuuuuuuuuuuu !

Nathann

[mpatel]

Please remember to update the Author(s) and Reviewer(s) fields. I've entered guesses. lsampaio, could you update ​the account-name map on the main Sage Trac wiki page with your information? Thanks!