Opened 10 years ago
Closed 10 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 everyj<i
, a neighbor colored withj
. This can define a Linear Program, which is used here to compute the Grundy number of a graph.
Nathann
Attachments (1)
Change History (5)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Status changed from needs_review to positive_review
comment:3 Changed 10 years ago by
Yeahhhhhhhhhhhhhhhhhhhh !!!!!!
Thank youuuuuuuuuuuuuu !
Nathann
comment:4 Changed 10 years ago by
- 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!
It works, the documentation is ok. I believe it can be accepted.