id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
17787 Wrong result returned by Graph.is_interval ncohen "It has been reported by Damian Bogdanowicz on sage-devel [1] that the interval graph recognition agorithm returns a wrong result:
{{{
sage: Graph('GvGNp?').is_interval()
True
}}}
This graph is not an interval graph as it contains an asteroidal triple (1,5,7).
The fix is rather short: some 'partial' pq-trees were handled like 'full' ones and that was wrong. As an additional check, we get the expected [2] number of interval graphs up to n=9 (takes ~10mn)
{{{
sage: n = 8
sage: count = [0]*(n+1)
sage: for g in graphs(n, augment='vertices',property= lambda x:x.is_interval()):
....: count[g.order()] += 1
sage: count
[1, 1, 2, 4, 10, 27, 92, 369, 1807, 10344]
}}}
Nathann
P.S.: The class, however, could definitely benefit from a more general rewrite. Another ticket (already half-written) will adress that and make the documentation and method names more explicit.
[1] https://groups.google.com/forum/#!topic/sage-combinat-devel/DnULBrlkgBc
[2] http://oeis.org/A005975" defect closed major sage-6.5 graph theory fixed dcoudert was dimpase Nathann Cohen Dima Pasechnik N/A b937842be6daaa63611f4ce4fef2238fcff65200 b937842be6daaa63611f4ce4fef2238fcff65200