#9619: b-coloring of a graph
----------------------------+-----------------------------------------------
Reporter: lsampaio | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.5.3
Component: graph theory | Keywords:
Author: lsampaio | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
> 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.
The list just above ensures that if `is_used[i]` is set to 1, then there
is at least one vertex colored with `i`. Beside, it is already an
equivalence as you are maximizing the sum of the is_used. If any of them
can be set to 1, it will, even without this constraint !
> 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)).
Ok !
I also noticed something wrong in the doc, sorry for mentionning it this
late : check out how the definition f `m(G)` is displayed... Probably just
a typo in the LaTeX string.
Short of these, everything is perfect ! The next version is the final one
`:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9619#comment:4>
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.
