Opened 11 years ago

Closed 11 years ago

#9619 closed enhancement (fixed)

b-coloring of a graph

Reported by: lsampaio Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.6
Component: graph theory Keywords:
Cc: ncohen Merged in: sage-4.6.alpha2
Authors: Leonardo Sampaio Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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

Attachments (1)

trac_9619.patch (7.8 KB) - added by lsampaio 11 years ago.
ticket 9619: function for the b-chromatic number of a graph (with corrections)

Download all attachments as: .zip

Change History (11)

comment:1 Changed 11 years ago by lsampaio

  • Cc ncohen added
  • Status changed from new to needs_review

comment:2 Changed 11 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:3 follow-up: Changed 11 years ago by lsampaio

  • Status changed from needs_work to needs_review

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

comment:4 in reply to: ↑ 3 Changed 11 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:5 Changed 11 years ago by lsampaio

  • Status changed from needs_work to needs_review

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.

comment:6 Changed 11 years ago by ncohen

  • Status changed from needs_review to positive_review

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

Thanksssssssssssssssssssssssssss !!!!

Nathann

comment:7 Changed 11 years ago by ncohen

  • Authors changed from lsampaio to Leonardo Sampaio
  • Reviewers set to Nathann Cohen

comment:8 Changed 11 years ago by mpatel

  • Status changed from positive_review to needs_work

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.

Changed 11 years ago by lsampaio

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

comment:9 Changed 11 years ago by lsampaio

  • Status changed from needs_work to positive_review

Updated !

comment:10 Changed 11 years ago by mpatel

  • Merged in set to sage-4.6.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.