#6660: Error in chromatic_number() and coloring() in the Graph class
--------------------------+-------------------------------------------------
Reporter: ncohen | Owner: rlm
Type: defect | Status: new
Priority: major | Milestone: sage-4.1.1
Component: graph theory | Keywords:
Reviewer: | Author:
Merged: |
--------------------------+-------------------------------------------------
Comment(by ncohen):
Answer from Rob Beezer on Sage-devel :
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:
* Color the 4-5-6 triangle with three colors.
* Color the 7-8-9 triangle with three colors where you will be forced to
color vertex 8 the same color as vertex 5.
* Vertex 1 is adjacent to 4, 6, 8, which now all have different colors,
forcing a fourth color for vertex 1.
* 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
... which is perfectly right ! It came from a mistake I made in the LP
relaxation... now fixed ! ;-)
This ticket can be deleted.
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6660#comment:3>
Sage <http://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
-~----------~----~----~----~------~----~------~--~---
