On Jul 30, 5:41 am, Nathann Cohen <nathann.co...@gmail.com> wrote:
> Trying to write a Linear Program version of the coloring problem, I
> found a graph ( pure luck, it was a RandomGNP ) for which the
> functions chromatic_number() and coloring() return a wrong value.
>
> sage: h=Graph(":I`ASWCaG`WaJC{afP")
> sage: h.chromatic_number()
> 4
> sage: h.coloring()
> [[6, 8], [9], [0, 4, 7, 3], [1, 2, 5]]
>
> with my version of the coloring() function I found a coloring using
> only 3 classes. As a proof, you can type which checks that each class
> is actually an independent set.
>
> for c in [[3, 9, 1], [9, 4, 0, 3], [3, 8, 5]]:
> print h.subgraph(c).connected_components_number()==len(c)
It appears to me that this graph has chromatic number 4. The three
classes given for a 3-coloring do not include every vertex and have
repeated vertices (namely 3 and 9). Try the following:
(a) Color the 4-5-6 triangle with three colors.
(b) Color the 7-8-9 triangle with three colors where you will be
forced to color vertex 8 the same color as vertex 5.
(c) Vertex 1 is adjacent to 4, 6, 8, which now all have different
colors, forcing a fourth color for vertex 1.
(d) The coloring from h.coloring() seems to check as a legitimate 4-
coloring.
As an aside, maybe the graph6 format doesn't work so well in Trac? The
back-ticks seem to have disappeared, leading to quite a different
graph. ;-)
Rob
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
