Opened 9 years ago

Closed 8 years ago

#9575 closed enhancement (fixed)

Grundy coloring of a graph

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.5.3
Component: graph theory Keywords:
Cc: Merged in: sage-4.5.3.alpha0
Authors: Nathann Cohen Reviewers: Leonardo Sampaio
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (1)

trac_9575.patch (10.0 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (5)

Changed 9 years ago by ncohen

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by lsampaio

  • Status changed from needs_review to positive_review

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

comment:3 Changed 8 years ago by ncohen

Yeahhhhhhhhhhhhhhhhhhhh !!!!!!

Thank youuuuuuuuuuuuuu !

Nathann

comment:4 Changed 8 years ago by mpatel

  • Authors set to Nathann Cohen
  • Merged in set to sage-4.5.3.alpha0
  • Resolution set to fixed
  • Reviewers set to Leonardo Sampaio
  • Status changed from positive_review to closed

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!

Note: See TracTickets for help on using tickets.