Ticket #9619 (closed enhancement: fixed)
b-coloring of a graph
|Reported by:||lsampaio||Owned by:||jason, ncohen, rlm|
|Report Upstream:||N/A||Reviewers:||Nathann Cohen|
|Authors:||Leonardo Sampaio||Merged in:||sage-4.6.alpha2|
This patch adds the function b_coloring, which computes a b-coloring with the maximum number of colors. Here are some explanations from the function's help :
Given a proper coloring of a graph G and a color class C such that none of its vertices have neighbors in all the other color classes, one can eliminate color class C by assigning distinct colors to each of its elements.
One can repeat this procedure until a coloring is obtained where every color class contains one vertex with neighbors in all the other color classes. We call such a vertex a b-vertex. So, one can define a b-coloring as a proper coloring where each color class has a b-vertex, a vertex with neighbors in all the other colors.
The worst-case behaviour of this procedure for eliminating color classes is the b-chromatic number of G (denoted \chi_b(G)): the maximum k such that G admits a b-coloring with k colors.
- Status changed from needs_work to needs_review
- Status changed from needs_review to needs_work
- Reviewers set to Nathann Cohen
- Authors changed from lsampaio to Leonardo Sampaio