b-coloring of a graph

[lsampaio]

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.

Leonardo

[ncohen]

Hello !!!

It's nice to be reviewing your first patch !

Well, a few comments about the documentation :

Unless you define what is a "maximum" b-coloring, the first line of the doc does not make sense (I understaned what you mean, but it has to be rephrased to be correct). Then it is 'a', not 'the', as there may be many. Then this b-cloring may not exist if k is less than Chi, so maybe you should even add "if possible".

by assigning distinct colors to each of its elements => assigning the mising color in its neighborhood

The second paragraph is not clear, perhaps you should first defie what a b-vertex is, then rephrase the whole section.

Define what you mean by "worst case" -> I know what it means, but then again I know what b-coloring is.

NOTE : Instead of copying what I wrote for he Grundy method, perhaps you should mention your degree-based bound, to say that it can be assumed to be optimal if it reaches this bound (which is less than the max degree of course).

What the hell is this ?

p.add_constraint(Sum(color[v][i] - is_used[i] for v in g.vertices()), max = 0) 

In the following

p.set_objective(Sum(is_used[i] for i in xrange(k))) 

classes = xrange(k)

And I think that's all there is ! By the way, if you know of a good b-coloring-specific example to add in the Examples section... I didn't have any inspiration for the Grundy number ;-)

Nathann

[lsampaio]

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)).

[ncohen]

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

[lsampaio]

Here is the (I suppose final) version of the patch. I made the changes in the constraints as sugested by Nathann and also corrected some mistakes in the documentation.

[ncohen]

I didn't think I would live to see it :-D

Thanksssssssssssssssssssssssssss !!!!

Nathann

[mpatel]

Could someone update the commit string of the patch so its first line is a < 80 (or so) character summary of the changes that includes the ticket number, then restore the positive review? Additional lines are no problem, of course.

[lsampaio]

ticket 9619: function for the b-chromatic number of a graph (with corrections)

[lsampaio]

Updated !