id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
11735,Bug in is_chordal,ncohen,tbd,"As reported by Jan on sage-devel [1], the current implementation of is_chordal is incorrect. Given a vertex v adjacent to x and y (x and y being non-adjacent), a shortest path between x and y in G-v does not necessarily avoid the neighbors of v. Clearly.
Well, with this patch the shortest path is computed in the graph G with v and all its neighbors removed with the exception of x and y, so that it can not happen again.
Besides, as it is almost free to check that the certificate is indeed a hole, this patch adds a test just in case `:-)`
Nathann
Requires :
* #11738
Apply:
* [attachment:trac_11735.patch]
[1] https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion",defect,closed,major,sage-4.8,graph theory,fixed,,lsampaio ddestrada dcoudert,sage-4.8.alpha4,Nathann Cohen,David Coudert,N/A,,,,,