#9619: b-coloring of a graph
----------------------------+-----------------------------------------------
Reporter: lsampaio | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.5.3
Component: graph theory | Keywords:
Author: lsampaio | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Changes (by lsampaio):
* status: needs_work => needs_review
Comment:
Hi Nathann,
I've the corrections you proposed, thank you.
Concerning the constraint
{{{p.add_constraint(Sum(color[v][i] - is_used[i] for v in g.vertices()),
max = 0) }}}
it is necessary because we only require that if is_used[i] then there is
a b-vertex with color i. But it could happen that a vertex v is such that
c[v][j] = 1, is_used[j] = 0 and j such that there are no b-vertices in it.
About the examples, I believe they are ok for the b-coloring, even if
they're not interesting for the Grundy number. The point is that the P_5
is a simples example where b(G) = m(G), and the Petersen graph is
relatively hard to calculate by hand, and it is an interesting example
where b(G) < m(G) (usually the other examples have many vertices with same
neighborhood to force b(G) < m(G)).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9619#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
